3
$\begingroup$

The ring Zn:={0,1,..,n-1} under addition and multiplication modulo n. Suppose a,b,c,x $\in$ Zn are nonzero and the cyclic order R(a,b,c) holds, then under what conditions does R(ax,bx,cx) hold ?

$\endgroup$
1
  • $\begingroup$ If and only if $R(a(-x),b(-x),c(-x)$ doesn't? :-) (Well at least if $x$ is a unit modulo $n$). I can't see there being any sensible general answer to this. $\endgroup$ May 21, 2010 at 17:27

2 Answers 2

4
$\begingroup$

Answer. Under the condition $$ \left\lbrace\frac{x(b-a)}n\right\rbrace<\left\lbrace\frac{x(c-a)}n\right\rbrace \qquad\qquad(*) $$ where $\lbrace\cdot\rbrace$ denotes the fractional part of a real number.

The condition $R(a,b,c)$ is equivalent to $R(0,b-a,c-a)$ and means that the least residues of $b-a$ and $c-a$ modulo $n$ are ordered in the increasing order as integers. Note that the least residue of an integer $m$ modulo $n$ can be expressed by means of $n\cdot\lbrace m/n\rbrace$.

The relations ($*$) are hardly related for different values of $x=1,2,\dots$: one can always construct $n$ and residues $a$ and $b$ in such a way that for a given range of $x\in X_1\cup X_2$ ($X_1$ and $X_2$ are two finite disjoint sets of $\mathbb Z_{>0}$) the inequality ($*$) hold for $x\in X_1$ and does not hold for $x\in X_2$.

$\endgroup$
4
  • $\begingroup$ So the answer doesn't depend on R(a,b,c) which means the question should have been "what is the most efficient way for an algorithm to check whether elements are in cyclic order?" and the answer is to change the cyclic relation to a linear relation by shifting 'a' back to zero. $\endgroup$ May 23, 2010 at 12:11
  • $\begingroup$ Yes, this would be the most appropriate question. And the answer I would prefer is $R(a,b,c)\iff\lbrace(b-a)/n\rbrace<\lbrace(c-a)/n\rbrace$. $\endgroup$ May 23, 2010 at 12:58
  • $\begingroup$ Although multiplication of all the elements by a factor does appear in the Dvornicich and Zannier paper in Charles Matthews answer. $\endgroup$ May 23, 2010 at 13:09
  • $\begingroup$ It appears in many other places (including my own articles) but this does not imply that the cases are related to the cyclic order. It's just a natural thing in the modular arithmetic to reduce residues to the least representatives. Note that Gauss proved the law of quadratic reciprocity by reducing residues to the absolutely least ones. $\endgroup$ May 23, 2010 at 14:27
1
$\begingroup$

There is some sort of theory for rational linear forms in fractional parts holding at all integer multiples prime to some denominator, by Dvornicich and Zannier: see Fractional parts of linear polynomials, Journal of the Australian Mathematical Society (2001), 70: 401-424. The place I know about where this issue comes up classically is the theory of the hypergeometric equation, namely Schwarz's list, as revisited by Landau and Errera. This application is mentioned in the paper, and is dealt with at length by a book of Matsuda.

In the nature of the whole discussion, one is trying to prove n is small if the fractional parts of several rational numbers with denominator n do not distribute themselves uniformly about under multiplication. It all looks like a messy combinatorial problem, but the example shows that sometimes there is a good or at least effective answer at the end.

$\endgroup$
1
  • $\begingroup$ Very interesting appearance of these inequalities. (page 419 or [19] of the paper). $\endgroup$ May 23, 2010 at 12:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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