If I have a mapping $d(x,y) = \min\{x-y, y-x\}$ where $x$ and $y$ are elements of $\mathbb{Z}_n$, how is this defined? For example, in $\mathbb{Z}_{6}$, $d(0,2) = \min\{-2, 2\}$. Since $-2 \equiv 4 \mod6$ I feel intuitively that the minimum should be considered to be $2$, but I'm not sure is this implicit in the definition of minimum, or do I have to define minimum to mean this separately somehow?
Asked
Active
Viewed 54 times
1 Answers
3
Think of the elements $0,1,...,n-1$ of $\mathbb{Z}_n$ as consecutive vertices of a regular $n$-gon.
Then the distance, as defined, is just the graph-theoretic distance, i.e., the least number of edges for a path between the two vertices.
In particular, in $\mathbb{Z}_6$, $d(0,2)$ equals $2$, not $4$.
The definition can be recast as $$ d(x,y)=\min\{(x-y)\;\text{mod}\;n,\;(y-x)\;\text{mod}\;n) \;\;\;\;\; $$ In particular, for $x,y\in\{0,1,...,n-1\}$, we get $$ d(x,y)= \begin{cases} 0&\text{if}\;x=y\\[4pt] \min\{(x-y),\; n-(x-y)\}&\text{if}\;x>y\\[4pt] \min\{(y-x),\; n-(y-x)\}&\text{if}\;y>x\\[4pt] \end{cases} $$
quasi
- 58,772
-
the graph-theoretic idea makes sense but I'm not sure I entirely understand the way you have written out d(x,y). It seems to me that this doesn't work if the two inputs x and y are separated by more than n. For example, if I replace 2 with 8, then I once again get a minimum of -2. Is this just due to me misunderstanding modular arithematic and they should always be considered to be within n of each other, or am I missing something? Thank you very much. – Jack Doherty Jun 13 '19 at 14:15
-
1You should assume $x,y\in{0,1,...,n-1}$. – quasi Jun 13 '19 at 15:00