Transcript Catalan pseudoprimes - Research in Scientific Computing in

Catalan pseudoprimes
Gary Davis
University of Massachusetts Dartmouth
September 2008
A Research in Scientific Computing in Undergraduate Education
(RESCUE)
talk under the auspices of
Computational Science for Undergraduate Mathematics Students
(CSUMS)
Two themes
• Computation can rapidly become hard and
require theory and new smart algorithms.
• Computation can provide insight into
phenomena that are not otherwise well
understood.
…one should
be unafraid to
ask “stupid”
questions…
Terry Tao
Catalan numbers
Named for Eugène Catalan (1814-1894)
Catalan’s minimal surface
Catalan numbers occur in many places:
# rooted binary trees with n two-children nodes (and
only two-children nodes have children):
Other interpretations
• # binary bracketings of n+1 letters.
((ab)c)d
(a(bc))d
(ab)(cd)
a((bc)d)
a(b(cd))
• # mountains that can be drawn with n upstrokes
and n downstrokes.
• # non-crossing handshakes across a round
table of 2n people.
• # ways a regular labeled (n+2)-gon can be
divided into n triangles.
• ... Hundreds of other interpretations
Calculating Catalan numbers
C(n) = nth Catalan number
C(n) = C(0)C(n-1)+C(1)C(n-2)+…+C(n-1)C(0)
1 = C(1) = C(0)C(0) so we have to have C(0) = 1
First few Catalan numbers: 1, 1, 2, 5, 14, 42, 132, 429,
1430, 4862, 16796, 58786, 208012, …
( )/
2n
From this (or otherwise) we get C(n) = n
(n+1)
Also, C(n) = 2(2n+1)C(n-1) = (4 - 6 )C(n-1)
n+2
n+2
C(n) ~ 4n/(n3/2) (from Stirling’s approximation to n!)
Behavior of C(n) (mod n)
{2, 0}, {3, 2}, {4, 2}, {5, 2}, {6, 0}, {7, 2}, {8, 6}, {9, 2}, {10, 6},
{11, 2}, {12, 4}, {13, 2}, {14, 6}, {15, 0}, {16, 6}, {17, 2}, {18,
6}, {19, 2}, {20, 0}, {21, 6}, {22, 6}, {23, 2}, {24,12}, {25, 2},
{26, 6}, {27, 20}, {28, 0}, {29, 2}, {30, 4}, {31, 2}, {32, 6}, {33,
9}, {34, 6}, {35, 7}, {36, 16}, {37, 2}, {38, 6}, {39, 20}, {40,
20}, {41, 2}, {42, 0}, {43, 2}, {44, 4}, {45, 0}, {46, 6}, {47, 2},
{48, 12}, {49, 2}, {50, 6}, {51, 3}, {52, 44}, {53, 2}, {54, 6},
{55, 32}, {56, 32}, {57, 39}, {58, 6}, {59, 2}, {60, 36}, {61, 2},
{62, 6}, {63, 12}, {64, 6}, {65, 5}, {66, 0}, {67, 2}, {68, 36},
{69, 66}, {70, 40}, {71, 2}, {72, 36}, {73, 2}, {74, 6}, {75, 45},
{76, 32}, {77, 0}, {78, 66}, {79, 2}, {80, 20}, {81, 20}, {82, 6},
{83, 2}, {84, 28}, {85, 65}, {86, 6}, {87,78}, {88, 0}, {89, 2},
{90, 40}, {91, 0}, {92, 24}, {93, 20}, {94,6}, {95, 5}, {96, 60},
{97, 2}, {98, 6}, {99, 66}, {100, 20}
Behavior of C((p-1)/2) (mod p) when p is prime think n=(p-1)/2 so p =2n+1
{3, 1}, {5, 2}, {7, 5}, {11, 9}, {13, 2}, {17, 2}, {19, 17}, {23, 21}, {29, 2}, {31, 29},
{37, 2}, {41, 2}, {43, 41}, {47, 45}, {53, 2}, {59, 57}, {61, 2}, {67, 65}, {71, 69}, …
-1
What happens
with p = 11
-2
0
2
9
Remainders
modulo 11
9  -2 (mod 11)
Modular arithmetic
1
10
3
8
4
7
6
5
What happens
commonly
If p is an odd prime number then
C((p-1)/2) leaves a remainder of:
(i) 2 if (p-1)/2 is even, and
Christian Aebi
(ii) p-2 if (p-1)/2 is odd
after division by p (Aebi & Cairns, 2008)
Grant Cairns
Using the language of congruences:
C((p-1)/2)  (-1)(p-1)/2 2 (mod p)
This is a very useful yet relatively elementary fact.
However …
5907 = 3  11 179 is NOT prime, but C(2953) =
2685461045769841051758766540085381778867958389653081570230102578743716557393414698432723201
8604835827481400079746180859042998847062904588628443988471656842884827176591322606447373374
5170114215990628802480728254509243027301515716578188638161845006186325509432566255514295371
1831244418616065082585704718306397738239043447166614877955581227181909058430031248348617076
0968127868566761148272338552874036538712642251864951401415652586599638696638057804060664559
6631653006201475028620345661154141255270151872832210794265662384373813424017601708284599405
4495818833422495660799118445511772765247271800099577968305312815044742826841617363657597852
8163599116161864412299568469979275279432984608037418232708341738407207027770560327790660034
4353295299852442860789606298468175396155772845257082370982362847442002490871840793567716393
7673814416315561113715624891227147234706544002599990688324334582933338390610996994739677497
3415359398078981156158196137589374662351141943852985025999036686058067386810262610494705052
3571552174904828327040289290338567727601984441556100643331078793265969915224311397883496585
7515412611408472976630522073617517592667108581311959437459287747863224966994092062028771177
7922309068740859670350741660990961665983693848404352130282562224098660358041153941329846724
1868755900937715786325565674536317167720777046580282235118578243566079815581931383398351037
7301387226791272498428158056445957968217325358883357983632452567265000599761691765728741331
1461344810948429374606549591272604279040292521129258067951756092432485416721762098130682725
4406072970389563344460445935199086302333484983795219149704548355624172580583495183269516446
6187793485557477665229404250105879530261145357869026594648791045680534059003041515103280103
14543270304179336612021901275279349103820000  2.7  101772
leaves a remainder of 5905 after division by 5907, and
5905  -2 (mod 5907)
Catalan pseudoprimes
These are odd non-primes 2n+1 such that:
C(n) = (-1)n2 (mod 2n+1)
5907 is one such – it’s the smallest. Are there more?
10932 = 1194649 and 35112 = 12327121
(1093 is the 183rd prime; 3511 is the 490th prime)
Currently - September 2008 - no others are known.
Are there finitely many or infinitely many?
Hard to find
We seek them here, we seek them there,
Mathematicians seek them everywhere.
Are they devilish? Are they sublime?
Those darned, elusive, pseudoprimes.
Emma Orczy
The problem is the exponential growth of the Catalan
numbers C(n) ~4n/(n3/2)
A bit of mathematical theory (Aebi & Cairns), plus
computation, was used to find 10932 & 35112: these are
of the form p2 where p is prime. Aebi & Cairns prove a
nice result that simplifies the search for numbers that are
squares of primes.
“Mathematicians
traditionally love to solve
problems by thinking.
Myself, I hate to think. I
love to meta-think, try to
do things, whenever
possible, by brute force,
and of course, let the
computer do the hard
work.
Doron Zeilberger, Rutgers
I just move around in the
mathematical waters,
thinking about things,
being curious, interested,
talking to people, stirring
up ideas; things emerge
and I follow them up. …I
have practically never
started off with any idea of
what I’m going to be doing
or where it’s going to go.
Michael Atiyah
Fields Medallist
Abel Laureate
Middle binomial coefficient
( )/
2n
C(n) = n
(n+1)
An odd nonprime 2n+1 is a Catalan pseudo
prime exactly when
2n
(-1)n n  1(mod 2n+1)
()
()
()
(-1)n
n
(-1)
f(n):=
2n
n
-1  0(mod 2n+1)
2n
n
-1  integer
2n+1
Behavior of a number theory function
ac(n):= f(n) (mod 1) =
( )
2n
(-1)n n -1 (mod 1)
2n+1
ac(p) = 0 if p is prime or a Catalan pseudoprime
ac(4):=
(-1)4
( ) -1
8
4
(mod 1)
2*4+1
= (8!/(4!4!)-1)/9 = ((8765/(432))-1)/9
= 69/9 = 7 2/3 = 2/3 (mod 1)
so ac(4) = 2/3
Plot of ac(n) versus 2n+1
Blow-up around 1/3
This line seems to be of
the form 1/3 + 1/p for
certain primes p
This line seems to be of
the form 1/3 - 1/q for
certain primes q
Cannot find k with ac(n) = 1/3. Tried 2n+1 < 195306.
Cannot – yet – prove there is no such n.
Blow-up around 1/5
This line seems to be of
the form 1/5 + 1/p for
certain primes p
This line seems to be of
the form 1/5 - 1/q for
certain primes q
ac(12) = 1/5 but cannot, so far, find any other
such n (and cannot – yet – prove there isn’t one).
ac(n) where 2n+1 = 35p, p prime
The primes 3 and 5
seem to be very special
in this respect
ac(n) where 2n+1 = 311p, p prime
This seems to be more
typical behavior
Values of ac(n): much information from
computation, many questions, few answers
(yet)
• The curves around 1/3 seem to be described by ac(3p)= 1/3
 1/p where p ranges over certain, but not all, primes? Is this
true? Which primes?
• Specific reduced fractional values of ac(n) seem to occur
relatively rarely. How can we quantify this? For example,
when 2n+1 is not prime the values of ac(n) repeat only about
0.015% of the time (n < 25000)
• Are there infinitely many n with ac(n) =2/3? n = 4 = 22 and
1144 = 231113 are two examples but there are no others
with n < 50000.
• Is there any value for ac(n), other than 0, that occurs more
than twice?
Breakthrough at University of Mass Dartmouth
New Catalan pseudoprime discovered
The End