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 gave a method for constructing cycles of 
any finite length using the Chinese Remainder Theorem.  To give some
background on this method, suppose the integers {A,B,C,D,E} constitute 
a solution cycle, and let x denote the 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 David's method of generating a solution cycle of length 5 (for 
example) is to 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.  It seems clear 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 we've assumed for any positive integer n there 
exists a set of n distinct primes p1 < p2 < .. < pn such that  
pn/p1 < (n+1)/(n-1).  Just for fun I checked to find the first 
occurrance of such sets.  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.

Anyway, David Einstein sent the following nice proof that there
is always a set of n primes with pn/p1 < (n+1)/(n-1):

 Assume that there are no sets with pn/p1 < (n+1)/(n-1).
 Then there are always less than n primes in the interval 
 {[(n+1)/(n-1)]^k to [(n+1)/(n-1)]^(k+1)}. But this 
 implies that the sum of 1/p is less than n * the sum 
 of [(n-1)/(n+1)]^k over k. This is a geometric series 
 which converges contradicting the fact that the sum of 
 (1/p) diverges.

So this completes the answer to question (1), proving that there 
exist solution cycles of length n for every positive integer n.

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
Сайт управляется системой uCoz