More Results on the Form xy (mod x+y)
Here's a summary of recent comments concerning integer sequences
generated by iterations of the function
f(x,y) = kxy (mod x+y) (1)
As discussed in Limit Cycles of xy (mod x+y), given any two positive
integers x[0] and x[1] we define a sequence by the recurrence x[n] =
f(x[n-1],x[n-2]), with the understanding that the least non-negative
residue is assigned at each stage, and the sequence terminates at the
kth term if x[k]=0.
The previous article treated only the case k=1, but in subsequent
discussions of other quadratic forms David Einstein observed that
every function of the form
f(x,y) = Ax^2 +Bxy + Cy^2 (mod x+y) (2)
is equivalent to one of the form kxy (mod x+y) with k = B-A-C, so I've
adopted the more general case.
The main questions that have been discussed are
(1) Do there exist solution cycles of length n for every
integer n?
(2) For which values of the parameter k is a divergent sequence
possible?
(3) Do there exist any "primitive" solution cycles other
than {5,7,11}, {7,5,11}, and {23,61,59,119,79,95}?
Regarding question (1) David suggested a method for constructing cycles
of any finite length using the Chinese Remainder Theorem. Suppose the
integers {A,B,C,D,E} constitute a solution cycle, and let x denote the
greatest common divisor (gcd) of A and B. If we put a=A/x and b=B/x
then by definition abx^2 = C (mod ax+bx). Clearly x must divide C, so
we have that gcd(A,B) divides gcd(B,C). Similarly, gcd(B,C) divides
gcd(C,D) and so on around the loop. Thus, each pair of consecutive
elements in a solution cycle has the same gcd, which we will call x.
This shows that every solution cycle of length 5 is of the form
{ax,bx,cx,dx,ex} where the integers a,b,c,d,e are coprime in
consecutive pairs. (They need not all be mutually coprime.) We can
cancel x out of each congruence of the form abx^2 = cx (mod ax+bx)
to give the system of linear congruences
(ab)x = c (mod a+b)
(bc)x = d (mod b+c)
(cd)x = e (mod c+d)
(de)x = a (mod d+e)
(ea)x = b (mod e+a)
Since a and b are coprime, it follows that ab is coprime to a+b,
etc, so we can certainly solve each individual congruence for x.
Furthermore, if the sums (a+b), (b+c), (c+d), (d+e) and (e+a) are
mutually coprime, then the Chinese Remainder theorem ensures
infinitely many simultaneous solutions of the form x=Mj+Q, where
M is the product of the moduli.
So, to generate a solution cycle of length 5 (for example), choose
a set of mutually coprime moduli m1,m2,m3,m4,m5 (where m1=(a+b), etc)
from which the corresponding values of a,b,c,d,e can be computed
from the formulas
a = (m1-m2+m3-m4+m5)/2
b = (m2-m3+m4-m5+m1)/2
c = (m3-m4+m5-m1+m2)/2
d = (m4-m5+m1-m2+m3)/2
e = (m5-m1+m2-m3+m4)/2
Assuming the resulting values of a,b,c,d,e are coprime in consecutive
pairs (including e,a), we are assured of a solution (infinitely many,
in fact) using the CRT. This method relies on the proposition that for
any given integer n we can construct a cycle of integers a,b,c,d... that
are coprime in consecutive pairs and such that all the sums mi of
consecutive terms are coprime. Here's a proof that this can in fact
always be done. The first step is the most interesting:
For any odd n select n distinct odd primes p1<p2<...<pn such that
pn/p1 < (n+1)/(n-1). Define the "sums" of the cycle as s1=2p1,
s2=2p2, ..., sn=2pn. The actual terms of the root cycle are then
v1 = p1 - p2 + p3 - ... + pn
v2 = p2 - p3 + p4 - ... + p1
v3 = p3 - p4 + p5 - ... + p2
etc
Clearly each v is odd and coprime to its immediate neighbors. Now
we set up the system of congruences
v1 v2 x = v3 (mod 2p1)
v2 v3 x = v4 (mod 2p2)
etc.
Recall that, by the CRT, if gcd(c,d)=1 then any congruence of
the form x = a (mod cd) is equivalent to the pair of congruences
x = a (mod c) and x = a (mod d). Therefore, since all the v are
odd, each of the above congruences can be split into two, one of
which is simply x=1 (mod 2). Thus, we need an odd solution of
the system
v1 v2 x = v3 (mod p1)
v2 v3 x = v4 (mod p2)
etc.
and we are assured of such a solution by the CRT. (Note that the
system solution is of the form x = Mk+U where M=p1*p2*..*pn and k
is any integer. Since M is odd, we can find an odd x for any U.)
Notice that the above construction relies on the fact that for any
positive integer n there exists an increasing sequence of n primes p1,
p2, ..., pn such that pn/p1 is less than (n+1)/(n-1). To prove this,
consider the sequence of real numbers [(n+1)/(n-1)]^k for k = 0,1,2,...
These values partition the real number line into segments, for each
of which the ratio of largest to smallest values is (n+1)/(n-1). If
the kth segment contains fewer than n primes, then the sum of the
reciprocals of the primes in that segment is less than n[(n-1)/(n+1)]^k.
It follows that the sum of the reciprocals of all the primes is less
than n times the geometric sum of [(n-1)/(n+1)]^k for k=0,1,2,..., which
converges. This contradicts the fact that the sum of the reciprocals
of the primes diverges. Hence, there must be segments containing n or
more primes.
So this completes the answer to question (1), proving that there exist
solution cycles of length n for every positive integer n. Just for
fun I checked to find the first occurrance of prime sets that satisfy
the requirements of the proof for each n. Here's what I found
n p1 ln(p1)/ln(n)
--- ---- ------------
2 2 1.0000
3 7 1.7712
4 19 2.1239
5 29 2.0922
6 53 2.2158
7 83 2.2708
8 127 2.3295
9 163 2.3182
10 223 2.3483
20 1181 2.3613
30 3163 2.3695
100 49169 2.3458
If p1(n) denotes the minimum p1 for a set satisfying the condition,
then it appears p1(n) = n^c where c is about 2.3.... So the
interesting question that arises out of all this is: What bounds
can be placed on the exponent c in the equation p1(n)=n^c ? I
suspect a certain tolerance would be equivalent to the Riemann
Hypothesis. The max value seems to occur at n=17 where c=2.403...
For the range of n values from 60 to 100 I find 2.3301 < c < 2.3682.
Question (2) concerns the possibility that the terms of a solution
sequence increase without limit. Here a suggestion from Peter Brown
led to consideration of arithmetic solution sequences, i.e., sequences
with terms of the form x[n]=sn+q for constants s and q. It turns out
that a sequence based on f(x,y) = kxy (mod x+y) has a solution of the
form x[n] = sn+q if and only if sk = -6 and qk is even. For example,
with k=1 we have descending solution sequences of the form x[n] =
-6n + u, where u = 0, 2, or 4. On the other hand, the recurrence
based on f(x,y) = x^2 + y^2 (mod x+y), which is equivalent to
f(x,y)=-2xy (mod x+y), has increasing (divergent) solution sequences
of the form x[n] = 3n + u, where u = 0, 1, or 2.
The answer to Question (3) turns out to be 'yes' by the brute force
search method. I found two more primitive cycles
(1271 3727 1343 3911)
(3527 4769 8259 5879 4271)
and David Einstein also found these two plus another
(11791 16057 15603 17383)
Notice that the Chinese Remainder method of generating solution
cycles tends to give cycles with very large common factors, roughly
in proportion to the product of all the sums of the coprime parts
of each pair of consecutive terms. In contrast, consider the
primitive solution cycle
{23,61,59,119,79,95}
This corresponds to the set of moduli
84 120 178 198 174 118
Since this cycle has an even period the moduli taken with alternating
signs must sum to zero, so there are just 5 degrees of freedom.
However, given these six moduli we have a free choice of one of the
individual terms. Choosing 23 for the first term we get the system
of congruences
(23)(61)x = 59 (mod 84)
(61)(59)x = 119 (mod 120)
(59)(119)x = 79 (mod 178)
(119)(79)x = 95 (mod 198)
(79)(95)x = 23 (mod 174)
(95)(23)x = 61 (mod 118)
which happens to have the solution x=1. (Of course there are really
infinitely many solutions x = 4221173880j + 1 for any integer j.)
I suppose there are primitive cycles of length n for every positive
integer n, but I don't know how to prove it. Interestingly, there
do not seem to be any more primitive cycles of length 3 besides
{5,7,11}. (See the article A Knot of Congruences and Problem #3
on the Most Wanted List.) Is the number of primitive solutions of
length n finite?
Return to MathPages Main Menu