LLT Digraph

[T.Rex]

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.)

[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.

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.

[T.Rex]

Hi maxal,

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 ?

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 ?

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

[maxal]

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.

Originally Posted by T.Rex

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).

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.

[maxal]

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

[T.Rex]

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

[maxal]

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.

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.

[T.Rex]

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

[maxal]

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]

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.

[T.Rex]

Sorry to answer late, I was in out of France.

Originally Posted by maxal

while 2^{q-1}-2 = 8189.

Since q=13, 2^(q-1)-2 = 4094.

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