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 
  (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

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)

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)

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


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