mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2006-04-25, 20:51   #1
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

13·73 Posts
Default 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^2-2) 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 well-known, 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^2-2 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 2006-04-25 at 20:54
T.Rex is offline   Reply With Quote
Old 2006-04-29, 03:43   #2
maxal
 
maxal's Avatar
 
Feb 2005

22×5×13 Posts
Default

One can show that the cycles in the LLT Digraph under the mapping x -> x^2-2 correspond to the cycles in the group Z_{2^(q-1)-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 1-cycles, one 2-cycle, and one 4-cycle.

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 self-conjugate cycle.

Denote by c(k) the number of k-cycles in Z_{2^(q-1)-1} and by c'(k) the number of self-conjugate k-cycles. Then the number of k-cycles 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[d|k] mu(k/d)*(2^d - 1) / k if k divides (q-1),
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 (q-1),
c'(2^t*s) = sum[d|s] mu(s/d)*2^{2^{t-1}*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 (q-1),
c'(2^t*s) = 0.

In order to simplify things consider two functions that do not depend on q:
c1(k) = sum[d|k] mu(k/d)*(2^d - 1) / k
c2(2^t*s) = sum[d|s] mu(s/d)*2^{2^{t-1}*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 k-cycles in the LLT Digraph for k dividing (q-1). 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 (q-1).
This happens when (q-1)/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 (q-1),
C(k) = c1(k) if k divides (q-1) and (q-1)/k is even number,
C(k) = c1(k) - c2(2k) = (c1(k) - c2(k))/2 if k divides (q-1) and (q-1)/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 2006-04-29 at 03:49
maxal is offline   Reply With Quote
Old 2006-04-29, 12:35   #3
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

13×73 Posts
Default

Hi maxal,
Quote:
Originally Posted by maxal
One can show that the cycles in the LLT Digraph under the mapping x -> x^2-2 correspond to the cycles in the group Z_{2^(q-1)-1} under the mapping x -> 2*x where elements x and -x are considered the same. ...
You are using several "one can show" and "it is easy to see", so the complete proof should be longer, but probably shorter than the one of ZetaX. However, this is very interesting. Thank you ! Do you plan to provide a LaTeX version or do you authorize me to add it in my paper ?

Quote:
Then the number of k-cycles in the LLT Digraph is C(k) = (c(k) - c'(k))/2 + c'(2k).
I do not clearly see the proof of this.


Do you think your method can be used to compute the DiGraph under the mapping x -> x^3-3x modulo a Mersenne prime ? (maybe a mapping x -> 3*x should be used ?)
My first experimental study seems to show that this Digraph_(x^3-3x)_modMqPrime is related to the Digraph_(x^2-2)_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^3-3x)_modMqPrime ?

Quote:
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.
Oh yes. I understand the property. But not clearly the proof.

Thanks !
Tony
T.Rex is offline   Reply With Quote
Old 2006-04-29, 15:07   #4
maxal
 
maxal's Avatar
 
Feb 2005

22·5·13 Posts
Default

Quote:
Originally Posted by T.Rex
Hi maxal,
You are using several "one can show" and "it is easy to see", so the complete proof should be longer, but probably shorter than the one of ZetaX. However, this is very interesting. Thank you ! Do you plan to provide a LaTeX version or do you authorize me to add it in my paper ?
It was just a sketch of the proof. The complete proof requires several lemmas on the structure of the field Z_{M_q}(sqrt(3)).
Feel free to add this sketch to the paper. I can edit/complete it later if you like.

Quote:
Originally Posted by T.Rex
Quote:
Then the number of k-cycles in the LLT Digraph is C(k) = (c(k) - c'(k))/2 + c'(2k).
I do not clearly see the proof of this.
Gluing each pair of elements x and -x into a single one contracts the cycles in Z_{2^(q-1)-1}. The contracted k-cycles are formed by:
1) pairs of conjugate k-cycles which glue into a single k-cycle under the contraction. The number of such pairs is (c(k) - c'(k))/2.
2) self-conjugate 2k-cycles which shrink their length by the factor of 2 under the contraction. The number of such cycles is c'(2k).

Quote:
Originally Posted by T.Rex
Do you think your method can be used to compute the DiGraph under the mapping x -> x^3-3x modulo a Mersenne prime ? (maybe a mapping x -> 3*x should be used ?)
I think it is related to the mapping x -> 3*x but in slightly more complicated ring. I will take a look at it.

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 2006-04-29 at 15:13
maxal is offline   Reply With Quote
Old 2006-04-29, 15:24   #5
maxal
 
maxal's Avatar
 
Feb 2005

10416 Posts
Default

btw,
c1(k) = A059966(k) (which looks more appropriate than A001037 mentioned in the paper)
c2(2k) = A000048(k)

Last fiddled with by maxal on 2006-04-29 at 15:28
maxal is offline   Reply With Quote
Old 2006-04-29, 15:35   #6
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

13·73 Posts
Default

Quote:
Originally Posted by maxal
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.
Moreover, the computation of the number of cycles of length L <= 16 for all Mersenne primes shows that if L is odd then there is only 1 possible value, while when L is even there are 2 possible values for the number of cycles of length L.

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
T.Rex is offline   Reply With Quote
Old 2006-04-29, 15:45   #7
maxal
 
maxal's Avatar
 
Feb 2005

22·5·13 Posts
Default

Quote:
Originally Posted by T.Rex
Moreover, the computation of the number of cycles of length L <= 16 for all Mersenne primes shows that if L is odd then there is only 1 possible value, while when L is even there are 2 possible values for the number of cycles of length L.

Also, for L=6, the value is 4 if q=3 mod 4 and 9 if q=1 mod 4.
All the above trivially follows from the formula

C(k) = 0 if k does not divide (q-1),
C(k) = c1(k) if k divides (q-1) and (q-1)/k is even number,
C(k) = c1(k) - c2(2k) = (c1(k) - c2(k))/2 if k divides (q-1) and (q-1)/k is odd number.

Quote:
Originally Posted by T.Rex
The number of cycles of length L even seems to depend on q mod 4.
That's not true. For example, if L is multiple of 4 then the number of cycles depends on q mod 8. If L is multiple of 8 then the number of cycles depends on q mod 16. etc.
maxal is offline   Reply With Quote
Old 2006-04-29, 15:51   #8
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

11101101012 Posts
Default

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^2-2 modulo a Mersenne prime" are given by g(n)=3^n+1/3^n, with 1 <= n <= 2^{q-1}-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 6-cycles 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
T.Rex is offline   Reply With Quote
Old 2006-04-29, 17:32   #9
maxal
 
maxal's Avatar
 
Feb 2005

22×5×13 Posts
Default

Quote:
Originally Posted by maxal
btw,
c1(k) = A059966(k) (which looks more appropriate than A001037 mentioned in the paper)
c2(2k) = A000048(k)
and
c1(k) - c2(2k) = A051841(k)
maxal is offline   Reply With Quote
Old 2006-04-29, 18:29   #10
maxal
 
maxal's Avatar
 
Feb 2005

22·5·13 Posts
Default

Quote:
Originally Posted by T.Rex
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^2-2 modulo a Mersenne prime" are given by g(n)=3^n+1/3^n, with 1 <= n <= 2^{q-1}-2 .
Something is wrong even from the counting arguments. According to Table 1 the total number of nodes in cycles is
2*1+1*2+2*3+1*4+9*6+165*12 = 2048 = 2^(q-2) (as expected)
while 2^{q-1}-2 = 8189.
It happens that the numbers 3^n+1/3^n modulo Mq with 1 <= n <= 2^{q-1}-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.
maxal is offline   Reply With Quote
Old 2006-05-08, 13:54   #11
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

3B516 Posts
Default

Sorry to answer late, I was in out of France.
Quote:
Originally Posted by maxal
while 2^{q-1}-2 = 8189.
Since q=13, 2^(q-1)-2 = 4094.
Quote:
It happens that the numbers 3^n+1/3^n modulo Mq with 1 <= n <= 2^{q-1}-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.
I've found the same value (456) for q=13. I've started a discussion with the authors of the paper.
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 Mq-1.
For q=13, Mq-1=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, Mq-1=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
T.Rex is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 22:53.


Mon Sep 25 22:53:07 UTC 2023 up 12 days, 20:35, 0 users, load averages: 0.81, 0.99, 1.01

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔