20060425, 20:51  #1 
Feb 2004
France
941 Posts 
LLT Digraph
Hello,
In the GIMPS Wiki, I've provided in November 2005 new properties about the number of cycles of length L under LLT (x^22) modulo a Mersenne prime. See: LLT Digraph. These properties require a clear and clean proof. Since the only proof I have is based on a discussion I had with a member of the AOPS forum: ZetaX, and since I am not able to understand many important details of the proof, I would be glad to get help from Number Theorists of the GIMPS forum to check, clean or improve the proof of ZetaX, who seems not interested in publishing his work. I have built a draft paper that describes the results, the proof of ZetaX, and the history of this "discovery" (seems a too big word, but I do not know another English word.) This draft is available as: PostScript .dvi Acrobat Since the .pdf version does not correctly displays a figure, I recommend you to download the .dvi or the .ps files. If there are volunteers to directly fix/improve the .tex file, the file is at: .tex, chapter 9 and 10. If you think this result is already wellknown, please let me know ! For other people not interested in reading/checking/improving the proof, they may be interested by the 2 new (to be confirmed) properties and also by the theorems of Shallit and Vasiga. My opinion is that studying the Cycles under LLT=x^22 modulo a Mersenne prime could provide useful information about the primality of a Mersenne number. There are also many properties to discover and prove, for the fun. Regards, Tony (Far from Internet from 04/30 till 05/07.) Last fiddled with by T.Rex on 20060425 at 20:54 
20060429, 03:43  #2 
Feb 2005
2^{2}·5·13 Posts 
One can show that the cycles in the LLT Digraph under the mapping x > x^22 correspond to the cycles in the group Z_{2^(q1)1} under the mapping x > 2*x where elements x and x are considered the same.
For example, let q=5. Then in Z_{15} we have the following cycles: 0 > 0 1 > 2 > 4 > 8 > 1 3 > 6 > 12 > 9 > 3 5 > 10 > 5 7 > 14 > 13 > 11 > 7 If elements x and x are considered the same then we have the following cycles: 0 > 0 1 > 2 > 4 > 8 > 1 and 7 > 14 > 13 > 11 > 7 represent the same cycle 3 > 6 > 12 > 9 > 3 becomes 3 > 6 > 3 5 > 10 > 5 becomes 5 > 5 i.e., there are two 1cycles, one 2cycle, and one 4cycle. We call "conjugate" cycles containing x and x for some x. In the example above, 1 > 2 > 4 > 8 > 1 and 7 > 14 > 13 > 11 > 7 are conjugate cycles while 3 > 6 > 12 > 9 > 3 is selfconjugate cycle. Denote by c(k) the number of kcycles in Z_{2^(q1)1} and by c'(k) the number of selfconjugate kcycles. Then the number of kcycles in the LLT Digraph is C(k) = (c(k)  c'(k))/2 + c'(2k). For q=5 we have c(1)=2, c(2)=1, c(4)=3 and c'(1)=0, c'(2)=1, c'(4)=1 implying C(1)=2, C(2)=1, C(4)=1. It easy to see that c(k) = sum[dk] mu(k/d)*(2^d  1) / k if k divides (q1), and c(k) = 0 otherwise. Similarly, one can show that 1) for odd s, c'(s) = 0 except c'(1)=1. 2) for odd s and for t>=1 such that 2^t*s divides (q1), c'(2^t*s) = sum[ds] mu(s/d)*2^{2^{t1}*d} / (2^t*s) for t>=1 and odd s. 3) for odd s and for t>=1 such that 2^t*s does not divide (q1), c'(2^t*s) = 0. In order to simplify things consider two functions that do not depend on q: c1(k) = sum[dk] mu(k/d)*(2^d  1) / k c2(2^t*s) = sum[ds] mu(s/d)*2^{2^{t1}*d} / (2^t*s) for t>=1 and odd s, and c2(k) = 0 for odd k>1 and c2(1)=1. It can be shown that c2(2*m) = (c1(m) + c2(m))/2 and, thus, (c1(k)  c2(k))/2 + c2(2k) = c1(k). Now let's compute the number of kcycles in the LLT Digraph for k dividing (q1). For such k, we have c(k)=c1(k) and c'(k)=c2(k) but not necessary c'(2k)=c2(2k) since 2k may not divide (q1). This happens when (q1)/k is odd number in which case the summand c2(2k) happens to be excessive implying C(k)=c1(k)c2(2k). Therefore, C(k) = 0 if k does not divide (q1), C(k) = c1(k) if k divides (q1) and (q1)/k is even number, C(k) = c1(k)  c2(2k) = (c1(k)  c2(k))/2 if k divides (q1) and (q1)/k is odd number. P.S. As an implication we have that Table 1 (in the paper) being continued to infinity in each column has at most 2 distinct numbers. Last fiddled with by maxal on 20060429 at 03:49 
20060429, 12:35  #3  
Feb 2004
France
3AD_{16} Posts 
Hi maxal,
Quote:
Quote:
Do you think your method can be used to compute the DiGraph under the mapping x > x^33x modulo a Mersenne prime ? (maybe a mapping x > 3*x should be used ?) My first experimental study seems to show that this Digraph_(x^33x)_modMqPrime is related to the Digraph_(x^22)_modMqPrime (D. Shanks talked about this fact but only about the LLT Tree ; not about the LLT Cycle). Can you give a look at this Digraph_(x^33x)_modMqPrime ? Quote:
Thanks ! Tony 

20060429, 15:07  #4  
Feb 2005
2^{2}·5·13 Posts 
Quote:
Feel free to add this sketch to the paper. I can edit/complete it later if you like. Quote:
1) pairs of conjugate kcycles which glue into a single kcycle under the contraction. The number of such pairs is (c(k)  c'(k))/2. 2) selfconjugate 2kcycles which shrink their length by the factor of 2 under the contraction. The number of such cycles is c'(2k). Quote:
It may be also interesting to consider the mapping x > x^2 + 2 which is likely similar to the mapping x > x^2  2. Last fiddled with by maxal on 20060429 at 15:13 

20060429, 15:35  #6  
Feb 2004
France
941 Posts 
Quote:
Also, for L=6, the value is 4 if q=3 mod 4 and 9 if q=1 mod 4. The number of cycles of length L even seems to depend on q mod 4. Tony 

20060429, 15:45  #7  
Feb 2005
2^{2}·5·13 Posts 
Quote:
C(k) = 0 if k does not divide (q1), C(k) = c1(k) if k divides (q1) and (q1)/k is even number, C(k) = c1(k)  c2(2k) = (c1(k)  c2(k))/2 if k divides (q1) and (q1)/k is odd number. Quote:


20060429, 15:51  #8 
Feb 2004
France
3AD_{16} Posts 
Oh. yes. Thanks. I looked at that too quickly and superficially.
T. By the way, I have a problem with the Theorem 17 on page 20 of paper "On the iteration of certain quadratic maps over GF(p)" of Shallit and Vasiga. Part (ii) says that the nodes of the cycles of the "digraph under x^22 modulo a Mersenne prime" are given by g(n)=3^n+1/3^n, with 1 <= n <= 2^{q1}2 . I'm experimenting with q=13, which has 9 cycles of length 6. Out of these 9 cycles, I've found that only 5 of these cycles have their elements generated by g(n). Here is a list of one element of each cycle: 288, 101, 532, 920, 2627 . The 4 other 6cycles starting with : 23, 722, 1812, 2255 have no element generated by g(n), even when 0 <= n <= 8191 . Do you see what have I missed ? Thanks, Tony 
20060429, 18:29  #10  
Feb 2005
2^{2}·5·13 Posts 
Quote:
2*1+1*2+2*3+1*4+9*6+165*12 = 2048 = 2^(q2) (as expected) while 2^{q1}2 = 8189. It happens that the numbers 3^n+1/3^n modulo Mq with 1 <= n <= 2^{q1}2 are not distinct. I have computed the actual number of distinct numbers of the form 3^n+1/3^n, it is 456 which is still different from 2048. 

20060508, 13:54  #11  
Feb 2004
France
941 Posts 
Sorry to answer late, I was in out of France.
Quote:
Quote:
For q=17, my computation is not ended, but it seems that it behaves as expected by their theorem. I've also found that there is a relationship between n such that N=(3^n+1/3^n modulo Mq) and the factors of Mq1. For q=13, Mq1=2.3^2.5.7.13 . And values of n (in: 3^n+1/3^n modulo Mq) that generates an element of cycles of length 6 are of the form: 2^k.x.7 with k=1..6 and x={1,3,5,7,11} . For q=17, Mq1=2.3.5.17.257 . And values of n (in: 3^n+1/3^n modulo Mq) that generates an element of cycles of length 8 are of the form: 2^k.x.3.5.17 or 2^k.y.3.257 (maybe other forms) with k=1..8 . A quick look at q=19 seems to say the same. Probably there is a simple rule ... Tony 
