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 ?
$\begingroup$
$\endgroup$
1
asked May 21, 2010 at 17:23
-
$\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$– Robin ChapmanCommented May 21, 2010 at 17:27
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
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$.
answered May 22, 2010 at 13:26
-
$\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$ Commented 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$ Commented 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$ Commented 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$ Commented May 23, 2010 at 14:27
$\begingroup$
$\endgroup$
1
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.
François G. Dorais
44.4k6 gold badges150 silver badges233 bronze badges
answered May 23, 2010 at 11:19
-
$\begingroup$ Very interesting appearance of these inequalities. (page 419 or [19] of the paper). $\endgroup$ Commented May 23, 2010 at 12:45