If there is a function $f(x) = x\bmod n$ and, whenever $0\leq x_1\lt x_2\lt n$, we have $f(x_1)\lt f(x_2)$, can we say that $f$ is increasing?

Also, when finally I prove that $f(x)$ is increasing, how do I say it is doing so "modular arithmetically". I want to be able to specify that the function is increasing by the definition of increasing functions that is used for modular arithmetic.

Disclosure: I'm not a mathematician: I'm a student programmer who loves math. I'm working on proving that a given algorithm satisfies the requirements for being a solution to the critical section problem. This is homework, but the answer to that question is not homework.



PS I post on stackoverflow but this is my first question here.

  • $\begingroup$ I think you mean "$x_1\lt x_2\Rightarrow f(x_1)\lt f(x_2)$", rather than what you wrote. $\endgroup$ – Arturo Magidin Mar 2 '12 at 5:12
  • $\begingroup$ What, exactly, is your domain and your codomain? Are you mapping to/from congruence classes, or residue representatives? $\endgroup$ – Arturo Magidin Mar 2 '12 at 5:13
  • $\begingroup$ It shouldn't be. Residues modulo $n$ don't have a natural notion of order (they do have an unnatural one given by the usual order on $\{ 0, ... n-1 \}$). $\endgroup$ – Qiaochu Yuan Mar 2 '12 at 5:15
  • $\begingroup$ I certainly did mean "x_1 < x_2 => f(x_1) < f(x_2)" but only so long as x < n. Whenever x = n f(x) will be zero, which is probably less than f(x - 1). This is the question. Actually, maybe my question is whether < is meaningful in modular arithmetic. @Arturo as I said I am not a mathematician, and I do not understand your question. f(x) takes an integer argument and the result is an integer? $\endgroup$ – Ziggy Mar 2 '12 at 5:23
  • $\begingroup$ As Qiaochu says, we do not usually consider the set of residue classes modulo $n$ (the results of applying the $\bmod n$ operator) to be ordered, because there is no order that has "nice properties." You can assign an arbitrary order and say that $f$ is "increasing" relative to that order, but if you just say that $f$ is "increasing", then nobody will understand that you mean the condition you have listed. So your best bet is to just state the condition explicitly: "If $0\leq x_1\lt x_2\lt n$ then $f(x_1)\lt f(x_2)$, where we order $\{0,1,2,\ldots,n-1\}$ with its usual order." $\endgroup$ – Arturo Magidin Mar 2 '12 at 5:27

Mathematicians don't usually put orderings on rings with positive characteristic, since we like to be able to say things like $x<x+1$ for all $x$.

But there's no reason you can't order the residue classes by setting $[x]<[y]$ whenever $0\leq x,y<n$. In other words, $[0]<[1]<\ldots <[n-1]$. Be careful though. For example, if this is your ordering mod 5, then $[-1]>[12]$ since $[-1]=[4]$ and $[12]=[2]$.

Just make sure that your ordering does not depend on which representative you pick from each class. (This is the definition of well-defined.)

As far as terminology goes, this is a nonstandard thing, so it's worth explaining your ordering. Then you can say "$f$ is increasing with respect to this ordering."

  • $\begingroup$ Hmm... I like where you are going with this, but did not understand your answer completely. From your first paragraph though I gather that the answer is "no, there is no concept of an increasing function in modular arithmetic"? In which case I'll have to say something like, f(x) is increasing, except where x = n? $\endgroup$ – Ziggy Mar 2 '12 at 5:26
  • $\begingroup$ Be wary of saying "$f(x)$ is increasing except where $x=n$," since I don't know if the exception is between $n$ and $n+1$ or between $n-1$ and $n$. It is best to explicitly define your ordering and say that the function is increasing with respect to the ordering. $\endgroup$ – Brett Frankel Mar 2 '12 at 5:29

If you want to have $x+1\gt x$ for all $x$, then there is no way to order the integers modulo $n$.

If you are willing to settle for $0\lt1\lt2\lt\cdots\lt n-1$, and you have a function with $x\lt y$ implying $f(x)\lt f(y)$, then your function can only be the identity function, $f(x)=x$ for all $x$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.