# Query regarding a Lemma from a paper.

This is from a paper. Let me introduce the required definitions and post my query:
Definition: A vector $\mathbf{x}$ is a $q$-dimensional vector of probabilities defined as $\mathbf{x}=(x_0,x_1,\dots ,x_{q-1})$; $\forall{i},x_i\geq0$; $\sum_{i=0}^{q-1}x_i=1$ . The indices $0,1,\dots,q-1$ are to be interpreted as elements from the finitie field $GF(q)$.
Definition: An operation $\mathbf{x}^{+g}\triangleq (x_g,x_{1+g},\dots,x_{(q-1)+g})$ for any element $g \in GF(q)$.
Definition: Another operation $\mathbf{x}^{\times g}\triangleq (x_0,x_{g},\dots,x_{(q-1).g})$ for any element $g \in GF(q)$.
The operations ${+g}$ and $\times g$ are reversible with analogous definitions $(\mathbf{x}^{+g})^{-g}=\mathbf{x}$ and similarly for $g \neq 0$, $(\mathbf{x}^{\times g})^{g^{-1}}=\mathbf{x}$.

Question: The question I have is about the following Lemma that the author states:
Lemma: For $g \in GF(q)\setminus \{0\}$ and $i \in GF(q)$, $(x^{+i})^{\times g}=(x^{\times g})^{+ (i.g^{-1})}$.
The proof, as the author says, is to be obtained by looking at a specific index $k$ on the 2 sides of the equation but I'm unable to prove it

My interpretation:
Take an element $x_k,k \in (0,1,\dots,q-1)$.
LHS: The element $x_k$ becomes $x_{(k+i).g}$
RHS: The element $x_k$ becomes $x_{k.g+i.g^{-1}}$
Are the above two equal?

• Caveat: the operations don't work on the components $x_k$, they permute their positions. Commented Nov 20, 2013 at 15:49
• And to be more precise, you seemed to think that they work on the subscripts, but they do work on the positions! For example $$(x_0,x_2,x_4,\ldots)^{+1}=(x_2,x_4,\ldots),$$ because $$(y_0,y_1,y_2,\ldots)^{+1}=(y_1,y_2,\ldots).$$ Here $y_1=x_2, y_2=x_4$ et cetera. Commented Nov 20, 2013 at 17:15

I think that you have misunderstood the definition of the two operations. The vectors $\mathbf{x}$ here are just functions from $GF(q)$ to the reals. Let us define addition mappings $$A_i:GF(q)\to GF(q), k\mapsto k+i$$ for all $i\in GF(q)$, and multiplication mappings $$M_g:GF(q)\to GF(q), k\mapsto kg$$ for all $g\in GF(q), g\neq 0$. The definitions on the vectors then mean $$\mathbf{x}^{+i}:=\mathbf{x}\circ A_i,$$ and $$\mathbf{x}^{\times g}:=\mathbf{x}\circ M_g.$$ Therefore $$(\mathbf{x}^{+i})^{\times g}=(\mathbf{x}\circ A_i)\circ M_g$$ and $$(\mathbf{x}^{\times g})^{+(i g^{-1})}=(\mathbf{x}\circ M_g)\circ A_{ig^{-1}}.$$ But $$(A_i\circ M_g)(k)=A_i(kg)=kg+i=(k+ig^{-1})g=M_g(k+ig^{-1})=M_g(A_{ig^{-1}}(k))$$ for all $k\in GF(q)$, so $A_i\circ M_g=M_g\circ A_{ig^{-1}}.$

The claim follows from this.

Another way of looking at it is the following. The component of $(\mathbf{x}^{+i})^{\times g}$ at position $k$ is the component of $\mathbf{x}^{+i}$ at position $kg$, which is the component of $\mathbf{x}$ at position $kg+i$.

Similarly the component of $(\mathbf{x}^{\times g})^{+(i g^{-1})}$ at position $k$ is the component of $\mathbf{x}^{\times g}$ at position $k+ig^{-1}$, which is also the component of $\mathbf{x}$ at position $kg+i$.

It is very easy to go astray here, been there :-), so I add an example. If $q=p$, then the field operations are just modular arithmetic. Then $$(x_0,x_1,\ldots,x_{p-1})^{\times (-1)}=(x_0,x_{p-1},x_{p-2},\ldots,x_1),$$ so $$\left((x_0,x_1,\ldots,x_{p-1})^{\times (-1)}\right)^{+1}=(x_0,x_{p-1},x_{p-2},\ldots,x_1)^{+1}=(x_{p-1},x_{p-2},\ldots,x_1,x_0).$$ because the $^{+1}$ operation simply rotates the components one position to the left.

As predicted, we get the same result from the calculations (here $g=-1, i=1$, so $ig^{-1}=-1$) $$(x_0,x_1,\ldots,x_{p-1})^{+ (-1)}=(x_{p-1},x_0,x_1,\ldots,x_{p-2})$$ and $$\left((x_0,x_1,\ldots,x_{p-1})^{+ (-1)}\right)^{\times(-1)} =(x_{p-1},x_0,x_1,\ldots,x_{p-2})^{\times(-1)} =(x_{p-1},x_{p-2},\ldots,x_1,x_0).$$ All because here $^{+1}$ operation simply rotates the components one position to the left, $^{+(-1)}$ rotates the components one position to the right, and $^{\times(-1)}$ reverses the order of the other components save the first.

• Isn't this what @Cameron suggested that might be the caveat behind the lemmas? The order of composition of the operators being different from what they appear to be like? Commented Nov 20, 2013 at 16:13
• +1: Deja vu! Have you posted this before? I was searching for this last night because I knew there was a good reason why the composition wasn't in the order it seemed that it should be. Commented Nov 20, 2013 at 16:15
• This is great ! For some reason it never occurred to me that I interpreted the definition very wrongly and wasted several hours on it. Thank you very much for the most awesome explanation ! Commented Nov 20, 2013 at 18:02