mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2022-03-16, 01:06   #12
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

22·52·61 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
I did say "any k". Powers k never seem to map x+1 to 1-x. HTH.
So you did. I just read "n" all the way through. Oops.

No good ideas for this question, either. At least not yet. I'm pretty sure I know how to get closed formulas for the coefficients of (1+x)^k (mod x^4 + 1), but I'm not sure they'd help much with the question at hand.
Dr Sardonicus is offline   Reply With Quote
Old 2022-03-16, 05:45   #13
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

29×151 Posts
Default

The companion matrix of x^4+1 is:

Code:
? cm=([0,0,0,-1;1,0,0,0;0,1,0,0;0,0,1,0])
                                                   
[0 0 0 -1]                                         
[1 0 0  0]                                         
[0 1 0  0]                                         
[0 0 1  0]
Then x+1 is equivalent to:

Code:
? cm+1                                     
                                                   
[1 0 0 -1]                                         
[1 1 0  0]                                         
[0 1 1  0]                                         
[0 0 1  1]
The determinant of this matrix is 2:

Code:
? matdet(cm+1)                                     
2
So is it safe to say a test of PRP test of x+1 over x^4+1 is necessarily a 2-PRP?

Answer: Yes, according to https://en.wikipedia.org/wiki/Determ..._matrix_groups

This makes verification to 2^64 easy. I/4 of odd n for n%8==5 and 8 Selfridges per test...

Verified to 2^64 using Feitsma's list of 2-PSPs.

Last fiddled with by paulunderwood on 2022-03-16 at 07:34
paulunderwood is offline   Reply With Quote
Old 2022-03-16, 12:17   #14
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

10111110101002 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
So is it safe to say a test of PRP test of x+1 over x^4+1 is necessarily a 2-PRP?
Quite safe. Here's another way to look at this:

If Mod(Mod(1,n)*x + 1, x^4 + 1)^n == Mod(1 - x, x^4 + 1)

taking the norm gives (Mod(2, n))^n = 2.

Quote:
Verified to 2^64 using Feitsma's list of 2-PSPs.
Well done, Sir!
Dr Sardonicus is offline   Reply With Quote
Old 2022-03-16, 18:07   #15
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

29×151 Posts
Default

FWIW, not a peep out of:

Code:
{forstep(n=5,1000000,8,
  if(!ispseudoprime(n),
    for(a=1,(n-1)/2,
      if(gcd(a,n)==1,
        Det=Mod(a,n)^4+1;
        if(Det^n==Det&&Mod(Mod(x+a,n),x^4+1)^n==a-x,
          print([n,a]))))));}

Last fiddled with by paulunderwood on 2022-03-16 at 18:16
paulunderwood is offline   Reply With Quote
Old 2022-03-17, 01:29   #16
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

22×52×61 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
You may be aware that no one has found a counterexample to the test Mod(Mod(x+2,n),x^2+1)^(n+1)==5 for n%4==3.
<snip>
BTW, similar to your observation with Mod(Mod(1,n)*x + 1, x^4 + 1),

Mod(Mod(1,n)*x + 2, x^2 + 1)^(n+1) == 5 implies 5^(n-1) == 1 (mod n) for n == 3 (mod 4) (assuming 5 does not divide n). That is, n is a Fermat pseudoprime to the base 5. I do not know if these have been as extensively computed as Fermat pseudoprimes to the base 2.

But my guess is, even if they haven't been, if you run the base 5 test first, and only run Mod(Mod(x+2,n),x^2+1)^(n+1)==5 on the composite survivors, that will speed things up.
Dr Sardonicus is offline   Reply With Quote
Old 2022-03-17, 13:22   #17
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

104338 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
BTW, similar to your observation with Mod(Mod(1,n)*x + 1, x^4 + 1),

Mod(Mod(1,n)*x + 2, x^2 + 1)^(n+1) == 5 implies 5^(n-1) == 1 (mod n) for n == 3 (mod 4) (assuming 5 does not divide n). That is, n is a Fermat pseudoprime to the base 5. I do not know if these have been as extensively computed as Fermat pseudoprimes to the base 2.

But my guess is, even if they haven't been, if you run the base 5 test first, and only run Mod(Mod(x+2,n),x^2+1)^(n+1)==5 on the composite survivors, that will speed things up.
Computing 5-PSPs up to 2^64 would be a mammoth task involving many dedicated years of running efficient code on big hardware. I think getting the list of 2-PSPs involved some mathematical tricks that I do not understand. All I can offer beyond my 2^50 check is a scan of Feitsma's sub-list of Carmichael numbers, which I just check up to 2^64 in less than a second, not counting the time to read the list into memory.
paulunderwood is offline   Reply With Quote
Old 2022-03-17, 14:06   #18
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

137248 Posts
Default

Let
Code:
v=[Mod(1/4, x^4 - 4*x^3 + 6*x^2 - 4*x + 2), Mod(-1/4*x^3 + 3/4*x^2 - 3/4*x + 1/4, x^4 - 4*x^3 + 6*x^2 - 4*x + 2), Mod(-1/4*x^2 + 1/2*x - 1/4, x^4 - 4*x^3 + 6*x^2 - 4*x + 2), Mod(-1/4*x + 1/4, x^4 - 4*x^3 + 6*x^2 - 4*x + 2)];
Then for k = 0, 3 the coefficient of x^k in lift(Mod(1+x, 1+x^4)^n) is trace(v[k+1]*x^n).

The only really "nice" expression is for the constant term, trace(Mod(1/4,x^4 - 4*x^3 + 6*x^2 - 4*x + 2)*x^n). This may be expressed as \frac{1}{4}\sum_{m=1}^{4}\(1 + e^{\frac{2\pi i(2m-1)}{8}\)^{n}

The coefficients all grow exponentially with n, with the ratio of consecutive terms approaching sqrt((2 + sqrt(2))).

Scratch that. The polynomial has two (complex conjugate) zeroes of absolute value sqrt(2 + sqrt(2)) and two of absolute value sqrt(2 - sqrt(2)). The expression is zero for n == 4 (mod 8).

What is true is that the n-th root of the absolute value of the n-th constant term has an upper limit of sqrt(2 + sqrt(2)).


Note: The polynomial x^4 - 4*x^3 + 6*x^2 - 4*x + 2 is charpoly(Mod(x+1,x^4 + 1)).

I wasn't advocating compiling a table of base-5 pseudoprimes. I was merely thinking that most composites would "flunk" a base-5 psp test, which (I am assuming) is much faster than the Mod(x+2,1+x^2) test. This would greatly reduce the number of slower Mod(2 + x, 1 + x^2) tests that needed to be done in searching for psp's for that test.

Last fiddled with by Dr Sardonicus on 2022-03-18 at 01:50 Reason: Fix bad notation;correct misstatement
Dr Sardonicus is offline   Reply With Quote
Old 2022-03-18, 15:02   #19
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

10111110101002 Posts
Default

As you can see from the following, I have obtained closed-form expressions for the coefficients of the degree-less-that-4 lift of Mod(1 + x, 1 + x^4)^n. They can be written as 4-term sums similar to the one already given. Unlike the constant term, though, the coefficient is a root of unity of degree greater than 1; a 4-th or 8-th root of unity. The trace may be written as a sum of algebraic conjugates; the conjugates of Mod(x, x^4 + 1) are Mod(x^3, x^4 + 1), Mod(-x, x^4 + 1), and Mod(-x^3, x^4 + 1). This allows the traces to be expressed as explicit 4-term sums. These expressions are unlikely to be useful computationally, but may be helpful theoretically.

Code:
? for(n=0,15,v=[lift(Mod(x + 1, x^4 + 1)^n),trace(Mod(-x, x^4 + 1)*Mod(1 + x, x^4+1)^n)/4, trace(Mod(-x^2, x^4 + 1)*Mod(x + 1, x^4 + 1)^n)/4, trace(Mod(-x^3, x^4 + 1)*Mod(x + 1, x^4 + 1)^n)/4, trace(Mod(x + 1, x^4 + 1)^n)/4];print(n" "v))
0 [1, 0, 0, 0, 1]
1 [x + 1, 0, 0, 1, 1]
2 [x^2 + 2*x + 1, 0, 1, 2, 1]
3 [x^3 + 3*x^2 + 3*x + 1, 1, 3, 3, 1]
4 [4*x^3 + 6*x^2 + 4*x, 4, 6, 4, 0]
5 [10*x^3 + 10*x^2 + 4*x - 4, 10, 10, 4, -4]
6 [20*x^3 + 14*x^2 - 14, 20, 14, 0, -14]
7 [34*x^3 + 14*x^2 - 14*x - 34, 34, 14, -14, -34]
8 [48*x^3 - 48*x - 68, 48, 0, -48, -68]
9 [48*x^3 - 48*x^2 - 116*x - 116, 48, -48, -116, -116]
10 [-164*x^2 - 232*x - 164, 0, -164, -232, -164]
11 [-164*x^3 - 396*x^2 - 396*x - 164, -164, -396, -396, -164]
12 [-560*x^3 - 792*x^2 - 560*x, -560, -792, -560, 0]
13 [-1352*x^3 - 1352*x^2 - 560*x + 560, -1352, -1352, -560, 560]
14 [-2704*x^3 - 1912*x^2 + 1912, -2704, -1912, 0, 1912]
15 [-4616*x^3 - 1912*x^2 + 1912*x + 4616, -4616, -1912, 1912, 4616]
If you want lift(lift(Mod(Mod(1,n)*x + 1, x^4 + 1)^k)) = (n-1)*x + 1, then trace(Mod(x + 1, x^4 + 1)^k)/4 has to be congruent to 1 (mod n); trace(Mod(-x^3, x^4 + 1)*Mod(x + 1, x^4 + 1)^k)/4 has to be congruent to -1 (mod n); and finally, trace(Mod(-x^2, x^4 + 1)*Mod(x + 1, x^4 + 1)^k)/4 and trace(Mod(-x, x^4 + 1)*Mod(1 + x, x^4+1)^k)/4 both have to be divisible by n.


EDIT: From the above data, you can see that for k == 6 (mod 8), the coefficient of x in lift((Mod(x + 1, x^4 + 1)^k) is zero; and if k == 4 (mod 8) the constant term is 0. I'm sure there's a straightforward proof, but I'm too lazy to work out the details

It is thus impossible to have lift(lift((Mod(Mod(1,n)*x + 1, x^4 + 1)^k)) = 1 - x for any n, if k is congruent to 4 or 6 (mod 8).

Last fiddled with by Dr Sardonicus on 2022-03-18 at 16:50
Dr Sardonicus is offline   Reply With Quote
Old 2022-03-20, 15:08   #20
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

22·52·61 Posts
Default "That's the stupidest proof I've ever seen in my life!"

I finally thought of a very simple, straightforward proof of the "zero-ness" of the coefficients of x^3, x^2, x and 1 in lift(Mod(x+1, x^4 + 1)^k) for k == 2, 0, 6 and 4 (mod 8) respectively.

All that is required is numerical verification that four consecutive values are 0. The rest being 0 then follows because for any given r, the subsequence lift(Mod(x+1,x^4 + 1))^(8*n + r) satisfies a linear recurrence with constant coefficients of order 4. Boom! Done.

The characteristic polynomial is charpoly(Mod(x, x^4 - 4*x^3+6*x^2-4*x+2)^8)) = x^4 + 272*x^3 + 18528*x^2 + 4352*x + 256.

The characteristic polynomial x^4 + 272*x^3 + 18528*x^2 + 4352*x + 256 factors as (x^2 + 136*x + 16)^2. I am too lazy to check whether any of the subsequences of terms in a residue class mod 8 actually satisfy a linear recurrence of order 2.
Dr Sardonicus is offline   Reply With Quote
Old 2022-03-20, 21:13   #21
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

10001000110112 Posts
Default

Powers of x over x^2-136*x+16 are interesting.

Mod(Mod(x,n),x^2-136*x+16)^(n+1)==16 is good for n%8==3 and n%8==5

I can also check Mod(Mod(x,n),x^2-136*x+16)^((n+1)/4)==2 for n%8==3, and Mod(Mod(x,n),x^2-136*x+16)^((n+1)/2)==4 for n%8==5.

The test Mod(Mod(x,n),x^2-136*x+16)^(n+1)==16 can be transformed into Mod(Mod(x,n),x^2-1154*x+1)^((n+1)/2)==1 for n%8={3, 5} for Fermat-2-PRP, making a quick check of Feitsma's 2^64 2-PRP possible.

As ever n%8==1 has psudoprimes. Without checking Feitsma, we now have simple tests for n%8 = {3,5,7}

Last fiddled with by paulunderwood on 2022-03-20 at 21:51
paulunderwood is offline   Reply With Quote
Old 2022-03-21, 13:14   #22
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

22×52×61 Posts
Default

For every integer r = 0 to 7, the sequence an = lift(Mod(x+1,x^4+1)^(8*n + r)), n = 0, 1, 2, ... satisfies the recurrence an+2+136*an+1 + 16*an = 0.

Thus, for any given r, the coefficients of 1, x, x^2 and x^3 in the lift are four sequences, each satisfying this recurrence. I have noted cases for even r where one of the four sequences is the zero sequence.

I note that the discriminant of the quadratic x^2 + 136*x + 16 is 1362 - 4*16 = 128*144 = 2*82*122.

Note that Mod(1 + x, 1 + x^2)^4 has the linear minimum polynomial x + 4 (that is, (1 + I)^4 = -4), and now we have that Mod(1 + x, 1 + x^4)^8 has the quadratic minimum polynomial x^2 + 136*x + 16. Hmm, that's funny...

I checked, and - sure enough! Mod(1 + x, 1 + x^8)^16 has a degree-4 minimum polynomial; and Mod(1 + x, 1 + x^16)^32 has a degree-8 minimum polynomial.

I'm sold. Mod(1 + x, 1 + x^(2k))^(2k+1) has minimum polynomial of degree 2k-1. Hmm, in every case so far, the zeroes of the minimum polynomial are real...

EDIT: Of course they're all real. And there's nothing special about powers of two. We have

1 + exp(2*I*pi/n) = exp(2*I*pi/(2*n))*[exp(-2*I*pi/(2*n)) + exp(2*I*pi/(2*n))] = exp(2*I*pi/(2*n))*2*cos(2*pi/(2*n)).

This is a 2n-th root of unity times a real number. Raising to the n-th power gives a real number.

Last fiddled with by Dr Sardonicus on 2022-03-21 at 13:39
Dr Sardonicus is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 14:31.


Sun Dec 4 14:31:30 UTC 2022 up 108 days, 12 hrs, 0 users, load averages: 1.26, 1.02, 0.88

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

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