Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 ?

share|improve this question
    
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. –  Robin Chapman May 21 '10 at 17:27
add comment

2 Answers

up vote 4 down vote accepted

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$.

share|improve this answer
    
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. –  Roy Maclean May 23 '10 at 12:11
    
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$. –  Wadim Zudilin May 23 '10 at 12:58
    
Although multiplication of all the elements by a factor does appear in the Dvornicich and Zannier paper in Charles Matthews answer. –  Roy Maclean May 23 '10 at 13:09
    
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. –  Wadim Zudilin May 23 '10 at 14:27
add comment

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.

share|improve this answer
    
Very interesting appearance of these inequalities. (page 419 or [19] of the paper). –  Roy Maclean May 23 '10 at 12:45
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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