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