Prime numbers and primality testing is a Restricted Group with 1137 members. Yahoo Groups Cyclotomic polynomial puzzles Phil Carmody Message 1 of 43 , May 9, 2009 ----------------------- Firstly, I'm using Phi(n) to represent the cyclotomic polynomial whose index is n, assuming n is non-squarefree, and using p,q,r,... for primes. It's well known that Phi(p) only have the coefficient 1. It's also well known that Phi(pq) have coefficients bounded in absolute value by 1. So here're the puzzles: 1a) What can be said about bounds on coefficients of Phi(pqr)? b) What's the assymptotic growth? c) For what pqr does Phi(pqr) have the largest coefficients (that you can find)? 2) As 1, but what if you restrict p,q,r to be simultaniously == 1 mod 4, or == 3 mod 4? Is there a significant difference between the two subsets? (Inspired by Gosper) 3a) Can you categorise p,q,r such that Phi(pqr) only has coefficients in {-1,0,1}? b) Can you find a bigger pqr with that property than anyone else? Enjoy! Phil -- () ASCII ribbon campaign () Hopeless ribbon campaign /\ against HTML mail /\ against gratuitous bloodshed [stolen with permission from Daniel B. Cristofani] Phil Carmody May 9, 2009 ----------------------- 2 offlist contributions... Show message history Phil Carmody May 10, 2009 ----------------------- --- On Sat, 5/9/09, Phil Carmody wrote: > 2 offlist contributions... Why's everyone only replying off-list? I'm having some interesting little sub-threads with various people, I'm sure they'd like to know what each other's saying... > --- On Sat, 5/9/09, Phil Carmody > > 3a) Can you categorise p,q,r such that Phi(pqr) only has > > coefficients in {-1,0,1}? > > b) Can you find a bigger pqr with that property than > > anyone else? For largest-smallest, lets place a stake in the ground at p=29 with n = 29*31*5393 = 4848307 It appears that swift evaluation of cyclotomic polynomials is the hard part - it requires large quantities of both CPU power and RAM. I wonder if there's a way using modular arithmetic, or even p-adic arithmetic to reduce the quantity of computation or storage. Phil David Broadhurst May 10, 2009 ----------------------- --- In primenumbers@yahoogroups.com, Phil Carmody asked: > Why's everyone only replying off-list? Perhaps because the mods have set that as the on-line default? I tried to reply, but maybe I forgot that trap. There is no way of telling, since the default reply is not even copied to oneself. Here goes again (sorry if it eventually appears twice): > 3a) Can you categorise p,q,r such that Phi(pqr) only has > coefficients in {-1,0,1}? > b) Can you find a bigger pqr with that property than > anyone else? pqr= 103534127524074104115541098969958708089926902711923091490097\ 001545810093892338679248846099390229911806167096020172161339\ 248099921117956336949559455817976090558652472327237037907245\ 079673380295270552412505821551314360478060083799787164050405\ 497609391864910896620579324752947949306589953853514558460087\ 480667962113549945569489945478510973601172041512307421653813\ 8676796204064794079723241321918976844647423 has a cyclotomic polynomial that is easily proven to be flat, once you have factorized pqr into its 3 constituent primes. Yet I believe that I am the only person in the world who can actually prove that Phi(pqr) is indeed flat, if the CIA has not yet spooked my hard drive. Proof: print(concat(isprime([p,q,r]),[pqr==p*q*r,r>q,q>p,Mod(r,q*p)^2==1])) [1, 1, 1, 1, 1, 1, 1] David (with thanks to Nathan) Phil Carmody May 10, 2009 ----------------------- --- On Sun, 5/10/09, David Broadhurst wrote: > Phil Carmody asked: > > > Why's everyone only replying off-list? > > Perhaps because the mods have set that as the on-line > default? > I tried to reply, but maybe I forgot that trap. > There is no way of telling, since the default > reply is not even copied to oneself. How on earth can any moderator make anyone select "reply to sender" rather than "reply to group", or whatever the two choices are labeled in your mail reader of choice? If I had mind control like that, I'd do far more nefarious things with it. > Here goes again (sorry if it eventually appears twice): > > > 3a) Can you categorise p,q,r such that Phi(pqr) only > has > > coefficients in {-1,0,1}? > > b) Can you find a bigger pqr with that property > than > > anyone else? > > pqr= [SNIP - ooops, accidentally deleted] > > has a cyclotomic polynomial that is easily proven to be > flat, > once you have factorized pqr into its 3 constituent > primes. > Yet I believe that I am the only person in the world > who can actually prove that Phi(pqr) is indeed flat, > if the CIA has not yet spooked my hard drive. > > Proof: > > print(concat(isprime([p,q,r]),[pqr==p*q*r,r>q,q>p,Mod(r,q*p)^2==1])) > [1, 1, 1, 1, 1, 1, 1] If my memory serves me right, before I accidentally deleted it, pqr was 165. So ? p=3;q=5;r=11; ? pqr=p*q*r; ? print(concat(isprime([p,q,r]),[pqr==p*q*r,r>q,q>p,Mod(r,q*p)^2==1])) [1, 1, 1, 1, 1, 1, 1] What a truly wondrous proof! And as a double-check, we can see that the largest absolute value of any coefficient in Phi(pqr) is 1: ? vecmax(abs(Vec(polcyclo(pqr)))) 2 Hmmm, how strange, let's triple-check... ? polcyclo(pqr) x^80 + x^79 + x^78 - x^75 - x^74 - x^73 - x^69 - x^68 - x^67 + x^65 + 2*x^64 + 2*x^63 + x^62 - x^60 - x^59 - x^58 - x^54 - x^53 - x^52 + x^50 + 2*x^49 + 2*x^48 + 2*x^47 + x^46 - x^44 - x^43 - x^42 - x^41 - x^40 - x^39 - x^38 - x^37 - x^36 + x^34 + 2*x^33 + 2*x^32 + 2*x^31 + x^30 - x^28 - x^27 - x^26 - x^22 - x^21 - x^20 + x^18 + 2*x^17 + 2*x^16 + x^15 - x^13 - x^12 - x^11 - x^7 - x^6 - x^5 + x^2 + x + 1 Two it is. I will admit I was using your "proof" as a criterion for restricting my search-space. However, Maximillian quite correctly pointed out that things that your "proof" disproves are in fact flat: ? p=5;q=11;r=53; time = 0 ms. ? pqr=p*q*r 2915 ? print(concat(isprime([p,q,r]),[pqr==p*q*r,r>q,q>p,Mod(r,q*p)^2==1])) [1, 1, 1, 1, 1, 1, 0] ? vecmax(abs(Vec(polcyclo(pqr)))) 1 So it's not as simple as either of us first thought. Phil David Broadhurst May 10, 2009 ----------------------- --- In primenumbers@yahoogroups.com, Phil Carmody wrote: > ? p=3;q=5;r=11; Yikes! Big sorry: this is the kosher proof: {print(concat(isprime([p,q,r]),[pqr==p*q*r,r>q,q>p, Mod(r,q*p)==1||Mod(r,q*p)==-1]))} [1, 1, 1, 1, 1, 1, 1] If that is all "1"s then it is a proof of flatness. So my 403-digit anti-CIA answer to (3b) is proven flat, by Theorem 1 in MR2351667 (2008k:11031) Kaplan, Nathan(1-PRIN) Flat cyclotomic polynomials of order three. (English summary) J. Number Theory 127 (2007), no. 1, 118--126. 11B83 (11C08 11N56) Nota Bene: Failure of this test does not imply non-flatness. Thanks, Phil, for spotting that (Mod(r,q*p)==1||Mod(r,q*p)==-1) != (Mod(r,q*p)^2==1) which was a really bad boob by me. David David Broadhurst May 10, 2009 ----------------------- --- In primenumbers@yahoogroups.com, Phil Carmody asked: > How on earth can any moderator make anyone select > "reply to sender" rather than "reply to group", > or whatever the two choices are labeled in your mail reader There was no mail reader. As I indicated, I was on-line, in the PrimeNumbers list, where the moderators have set the default in the "reply form" as "reply to sender". And after typing my message, I forgot to countermand their unfriendly default at the top of the form. The moderators in the PrimeForm list are much more collegial, since there they have set the default to "reply to list". I got so used to this in the past that I keep forgetting how unfriendly the PrimeNumbers list has been made, with no public list of contributors and a weird default for reply. I think there must be a "control freak" among the mods? Fortunately s/he did not get to cripple the PrimeForm list. David (on line, on list, eventually remembering to countermand the default at top of the reply form) Maximilian Hasler May 10, 2009 ----------------------- With Kaplan's T.1, we have a sufficient criterion allowing to construct arbitrarily large "odd flatphi"s of order 3, so the part (3b) of the initial puzzle is cooked (AFAICS). However, the (3a) still seems open, in particular my concern of (efficiently) counting *all* of them, i.e. A159909(n) = #{ (p,q) with odd primes p wrote: > > --- In primenumbers@yahoogroups.com, > Phil Carmody asked: > > > How on earth can any moderator make anyone select > > "reply to sender" rather than "reply to group", > > or whatever the two choices are labeled in your mail reader > > There was no mail reader. As I indicated, I was on-line, in > the PrimeNumbers list, where the moderators have set the > default in the "reply form" as "reply to sender". And after > typing my message, I forgot to countermand their unfriendly > default at the top of the form. The web interface is pants. The 1 'reply' link followed by _3_ choices of destination makes very little sense at all. Phil (Using the web interface just to see how bad it is) Phil Carmody May 10, 2009 ----------------------- -- On Sun, 5/10/09, David Broadhurst wrote: > Phil Carmody wrote: > > > ? p=3;q=5;r=11; > > Yikes! Big sorry: this is the kosher proof: > > {print(concat(isprime([p,q,r]),[pqr==p*q*r,r>q,q>p, > Mod(r,q*p)==1||Mod(r,q*p)==-1]))} > > [1, 1, 1, 1, 1, 1, 1] > > If that is all "1"s then it is a proof of flatness. > So my 403-digit anti-CIA answer to (3b) is proven flat, > by Theorem 1 in > MR2351667 (2008k:11031) > Kaplan, Nathan(1-PRIN) > Flat cyclotomic polynomials of order three. (English summary) > J. Number Theory 127 (2007), no. 1, 118--126. > 11B83 (11C08 11N56) > > Nota Bene: Failure of this test does not imply non-flatness. So, thanks to your fastidious literature scouring, we have part of (3a) now, and thus an infinite family to exclude from (3b). Not having read Kaplan yet, I don't if he categorises what's left after the removal of the easy ones... > Thanks, Phil, for spotting that > > (Mod(r,q*p)==1||Mod(r,q*p)==-1) != (Mod(r,q*p)^2==1) > > which was a really bad boob by me. Almost certainly one I've made myself. A centrelift squared would do the job if you want to avoid the ||. Phil Makoto Kamada May 10, 2009 ----------------------- On 2009/05/10 19:08, Phil Carmody wrote: > For largest-smallest, lets place a stake in the ground at p=29 with > n = 29*31*5393 = 4848307 Smaller n at p=29 n = 29*59*1709 = 2924099 q=nextprime(p), smallest r n = 2*3*5 = 30 n = 3*5*29 = 435 n = 5*7*71 = 2485 n = 7*11*307 = 23639 n = 11*13*571 = 81653 n = 13*17*443 = 97903 n = 17*19*647 = 208981 n = 19*23*1747 = 763439 n = 23*29*4001 = 2668667 n = 29*31*5393 = 4848307 n = 31*37*2293 = 2630071 n = 37*41*6067 = 9203639 n = 41*43*3527 = 6218101 n = 43*47*24251 = 49011271 n = 47*53*14947 = 37232977 n = 53*59*31271 = 97784417 I found them by using a brute force method. Makoto Kamada Maximilian Hasler May 10, 2009 ----------------------- --- In primenumbers@yahoogroups.com, Makoto Kamada wrote: > Smaller n at p=29 > n = 29*59*1709 = 2924099 > > q=nextprime(p), smallest r > n = 2*3*5 = 30 > n = 3*5*29 = 435 > n = 5*7*71 = 2485 > n = 7*11*307 = 23639 > n = 11*13*571 = 81653 > n = 13*17*443 = 97903 ... > n = 53*59*31271 = 97784417 Congratulations! I also had this idea, but less (brute) force... Did we already have this: Smallest p*q*r for given p, 2 * 3 * 5 = 30 3 * 7 * 11 = 231 5 * 7 * 71 = 2485 7 * 13* 181 = 16471 11* 23* 251 = 63503 13* 17* 443 = 97903 ... Or the 3rd variant: smallest r for given p, 2 * 3 * 5 = 30 3 * 7 * 11 = 231 5 * 11 * 53 = 2915 7 * 71 * 83 = 41251 ... Maximilian Phil Carmody May 11, 2009 ----------------------- --- On Mon, 5/11/09, Makoto Kamada wrote: > > For largest-smallest, lets place a stake in the > > ground at p=29 with n = 29*31*5393 = 4848307 > > Smaller n at p=29 Aha - given that dirichlet proves that there's always a suitable r, there's little point in rewarding just searching in a straight line. So minimusing q*r for each p does make sense. > n = 29*59*1709 = 2924099 Interestingly, this isn't of Kaplan's r==+/-1 (mod pq) examples, as r == -2 (mod pq) > q=nextprime(p), smallest r Applying David's Kaplan +/-1 test: ? test(pqr)=local(f=factor(pqr));(f[3,1]+1)%(f[2,1]*f[1,1])-1 ? test(30) -1 ? test(435) -1 ? test(2485) 1 ? test(23639) -1 ? test(81653) -1 ? test(97903) 1 ? test(208981) 1 ? test(763439) -1 ? test(2668667) -1 ? test(4848307) -1 ? test(2630071) -1 ? test(9203639) -1 ? test(6218101) 1 ? test(49011271) -1 ? test(37232977) 1 ? test(97784417) 1 > I found them by using a brute force method. Did you just follow the Kaplan +/-1 construction, or did you look elsewhere? Phil Makoto Kamada May 11, 2009 ----------------------- On 2009/05/11 16:00, Phil Carmody wrote: > Did you just follow the Kaplan +/-1 construction, or did you look elsewhere? I did not know the Kaplan's... I just calculated cyclotomic polynomials and checked coefficients of them for each n from p*q*nextprime(q) to p*q*r after I read your puzzle. Makoto Kamada Phil Carmody May 11, 2009 ----------------------- --- On Mon, 5/11/09, Makoto Kamada wrote: > On 2009/05/11 16:00, Phil Carmody wrote: > > Did you just follow the Kaplan +/-1 construction, or > > did you look elsewhere? > > I did not know the Kaplan's... > I just calculated cyclotomic polynomials and checked > coefficients of them > for each n from p*q*nextprime(q) to p*q*r after I read your > puzzle. Excellent, that seems to indicate that the large majority of them are of Kaplan's +/-1 form, which in turn makes the counter-examples, ones not of that form, more interesting. Phil David Broadhurst May 11, 2009 ----------------------- --- In primenumbers@yahoogroups.com, Phil Carmody wrote: > > n = 29*59*1709 = 2924099 > r == -2 (mod pq) Conjecture [Broadhurst]: If p, q = 2*p +1, r = p*q - 2 are all prime, then Phi(p*q*r) is flat. Testing: [3, 7, 19] is flat [5, 11, 53] is flat [11, 23, 251] is flat [23, 47, 1079] ??? Bang goes Pari-GP [29, 59, 1709] is flat according to Makoto Kamada ??? Bang goes Pari-GP: GP/PARI CALCULATOR Version 2.4.2 (development) amd64 running linux (x86-64 kernel) 64-bit version compiled: Jun 12 2007, gcc-3.4.6 20060404 (Red Hat 3.4.6-8) parisize = 400000000, primelimit = 20000000 ? vm(n)=vecmax(abs(Vec(polcyclo(n)))) \\ brute force ? {forprime(p=3,23,q=2*p+1;if(isprime(q),r=p*q-2; if(isprime(r,print([p,q,r,vm(p*q*r)])))))} [3, 7, 19, 1] [5, 11, 53, 1] [11, 23, 251, 1] [23, 47, 1079, 39] ? gettime %1 = 760803 ? Help! The height must be less than p as was proven by A. S. Bang in 1895. So GP's "39" with p = 23 must be wrong. Help! Can someone please compute the height of Phi(23*47*1079) ? David (brute-force failure) David Broadhurst May 11, 2009 ----------------------- --- In primenumbers@yahoogroups.com, "David Broadhurst" wrote: > [23, 47, 1079] ??? Bang goes Pari-GP Hmm. Bang go Broadhurst's brackets: > if(isprime(r,print([p,q,r,vm(p*q*r)])))))} ? print(factor(1079)[,1]~) [13, 83] So let's try again: vm(n)=vecmax(abs(Vec(polcyclo(n)))) \\ brute force {forprime(p=3,23,q=2*p+1;if(isprime(q),r=p*q-2; if(isprime(r),print([p,q,r,vm(p*q*r)]))))} [3, 7, 19, 1] [5, 11, 53, 1] [11, 23, 251, 1] Ah, that feels better! > Conjecture [Broadhurst]: > If p, q = 2*p +1, r = p*q - 2 are all prime, > then Phi(p*q*r) is flat. is intact: [3, 7, 19] is flat [5, 11, 53] is flat [11, 23, 251] is flat [29, 59, 1709] is flat according to Makoto Kamada David (bracket boober) Phil Carmody May 11, 2009 ----------------------- Quoth DJB: > vm(n)=vecmax(abs(Vec(polcyclo(n)))) \\ brute force > {forprime(p=3,23,q=2*p+1;if(isprime(q),r=p*q-2; > if(isprime(r),print([p,q,r,vm(p*q*r)]))))} > > [3, 7, 19, 1] > [5, 11, 53, 1] > [11, 23, 251, 1] > > Ah, that feels better! Dare I posit [23, 47, 14051]? I don't have enough RAM to put GP on the problem. I think it's time to write some custom Phi(pqr) code. If anyone has any already, please feel free to share. P-adics look like the future, but I've not written anything yet. Phil David Broadhurst May 11, 2009 ----------------------- --- In primenumbers@yahoogroups.com, Phil Carmody wrote: > Dare I posit [23, 47, 14051]? But then why not also [23, 47, 5407]? Conjecture 2 [Broadhurst-Carmody]: If [p,q,r] is a triplet of odd primes with q = 2*p + 1 and r = +/- 2 mod p*q, then Phi(p*q*r) is flat. Using an undisclosed (and possibly faulty) procedure, called "hpc", I found these (hopefully) flat guys: allocatemem(800000000);gettime; {forprime(p=3,29,q=2*p+1;if(isprime(q),forstep(s=-1,1,2, r=p*q+2*s;while(r<2*10^4,if(isprime(r), print([p,q,r,hpc(p*q*r)]);break(),r=r+p*q)))))} [3, 7, 19, 1] [3, 7, 23, 1] [5, 11, 53, 1] [5, 11, 167, 1] [11, 23, 251, 1] [11, 23, 761, 1] [23, 47, 14051, 1] [23, 47, 5407, 1] [29, 59, 1709, 1] [29, 59, 15401, 1] print(gettime" ms") 156413 ms David David Broadhurst May 11, 2009 ----------------------- --- In primenumbers@yahoogroups.com, "David Broadhurst" wrote: > Conjecture 2 [Broadhurst-Carmody]: > If [p,q,r] is a triplet of odd primes > with q = 2*p + 1 and r = +/- 2 mod p*q, > then Phi(p*q*r) is flat. Stronger yet is this: Conjecture 3 [Broadhurst]: If [p,q,r] is a triplet of odd primes with q > p and r = +/- 2 mod p*q, then Phi(p*q*r) is flat if and only if q = 1 mod p. Flat examples: [13, 79, 3079], [13, 79, 3083], [13, 157, 2039]. David Maximilian Hasler May 11, 2009 ----------------------- > Conjecture 3 [Broadhurst]: > If [p,q,r] is a triplet of odd primes > with q > p and r = +/- 2 mod p*q, > then Phi(p*q*r) is flat if and only if q = 1 mod p. > > Flat examples: [13, 79, 3079], [13, 79, 3083], [13, 157, 2039]. If I had the time to make some tests and to double-check that this is not a trivial statement, I'd conjecture that for q = +- 2 (mod p), Phi(pqr) is flat iff r=+-1 (mod pq). Any comments ? Specifically, are there any faulty in the following ? [5, 7, 71, 1, 1][5, 17, 509, -1, -1][5, 37, 739, -1, -1] [5, 47, 941, 1, 1][5, 67, 2011, 1, 1][5, 97, 971, 1, 1] [5, 107, 1069, -1, -1][5, 127, 2539, -1, -1][5, 137, 2741, 1, 1] [5, 157, 1571, 1, 1][5, 167, 1669, -1, -1][5, 197, 7879, -1, -1] [5, 227, 2269, -1, -1][5, 277, 8311, 1, 1][5, 307, 9209, -1, -1] [5, 317, 3169, -1, -1][5, 337, 3371, 1, 1][5, 347, 3469, -1, -1] [5, 367, 3671, 1, 1][5, 467, 9341, 1, 1][5, 487, 4871, 1, 1] [5, 547, 5471, 1, 1][5, 557, 5569, -1, -1][5, 587, 5869, -1, -1] [5, 647, 6469, -1, -1][5, 827, 8269, -1, -1][5, 937, 9371, 1, 1] [5, 977, 9769, -1, -1][7, 23, 643, -1, -1][7, 37, 1553, -1, -1] [7, 79, 2213, 1, 1][7, 107, 1499, 1, 1][7, 149, 2087, 1, 1] [7, 163, 2281, -1, -1][7, 191, 5347, -1, -1][7, 233, 9787, 1, 1] [7, 443, 6203, 1, 1][7, 457, 6397, -1, -1][7, 541, 7573, -1, -1] [11, 13, 571, -1, -1][11, 79, 8689, -1, -1][11, 101, 2221, -1, -1] [11, 167, 3673, -1, -1][11, 211, 4643, 1, 1][11, 409, 8999, 1, 1] [13, 41, 2131, -1, -1][13, 67, 1741, -1, -1][17, 19, 647, 1, 1] [17, 53, 1801, -1, -1][17, 223, 7583, 1, 1][17, 257, 8737, -1,-1] [19, 59, 2243, 1, 1][19, 211, 8017, -1, -1][23, 163, 7499, 1, 1] [29, 31, 5393, -1, -1][31, 157, 9733, -1, -1][37, 113, 8363, 1, 1] [41, 43, 3527, 1, 1] Maximilian Maximilian Hasler May 11, 2009 ----------------------- > If I had the time to make some tests and to double-check that > this is not a trivial statement, I'd conjecture that... (Sorry, it *is* trivial, from Kaplan's result.) I'll shup up now! David Broadhurst May 11, 2009 ----------------------- --- In primenumbers@yahoogroups.com, "David Broadhurst" wrote: > Conjecture 3 [Broadhurst]: > If [p,q,r] is a triplet of odd primes > with q > p and r = +/- 2 mod p*q, > then Phi(p*q*r) is flat if and only if q = 1 mod p. > > Flat examples: [13, 79, 3079], [13, 79, 3083], [13, 157, 2039]. Conjecture 4 [Sufficient congruences for flatness]: Let [p,q,r] be a triplet of primes with r > q > p > 2. Let w be the smallest positive integer such that r = +/- w mod p*q. If both of the congruences p = 1 mod w ... (1) q = 1 mod w*p ... (2) hold, then I conjecture that Phi(p*q*r) is flat. Nota Bene: The congruences are not necessary, since [3, 7, 11], with w = 10, is flat. The second congruence is not necessary when w = 1. I conjecture that it is necessary and sufficient when w = 2. Tests: Kaplan proved that, for any given p and q, the height of Phi(p*q*r) is determined by w. Thus flatness of [p, q, r] may be established by finding the smallest prime, s, with s = +/- r mod p*q and showing that [p, q, s] is flat. Thanks to this simplification, I have shown that any counterexample to Conjecture 4 must have p*q*r > 25*10^6. Flat examples: [23, 47, 14051] with w = 2 proven flat in 39809 ms [13, 157, 8167] with w = 3 proven flat in 43412 ms [17, 137, 6983] with w = 4 proven flat in 42567 ms [11, 331, 21841] with w = 5 proven flat in 198113 ms [19, 229, 4357] with w = 6 proven flat in 54054 ms [17, 409, 6961] with w = 8 proven flat in 126749 ms [11, 331, 3631] with w = 10 proven flat in 33204 ms [13, 313, 4057] with w = 12 proven flat in 42027 ms David Phil Carmody May 11, 2009 ----------------------- --- On Tue, 5/12/09, David Broadhurst wrote: > --- In primenumbers@yahoogroups.com, > > "David Broadhurst" wrote: > > > Conjecture 2 [Broadhurst-Carmody]: > > If [p,q,r] is a triplet of odd primes > > with q = 2*p + 1 and r = +/- 2 mod p*q, > > then Phi(p*q*r) is flat. > > Stronger yet is this: > > Conjecture 3 [Broadhurst]: > If [p,q,r] is a triplet of odd primes with q > p and r = +/- 2 mod p*q, > then Phi(p*q*r) is flat if and only if q = 1 mod p. > > Flat examples: [13, 79, 3079], [13, 79, 3083], [13, 157, 2039]. Nice. The following flip of axes is false: If p -flat flatness all coefficients satisfy abs(c)<=flatness -high height at least one coefficient satisfies abs(c)>=height -p p1[,p2] p1<=p<=p2 -q q1[,q2] q1<=q<=q2 -r r1[,r2] r1<=r<=r2 -qnext k1[,k2] q=nextprime^k(p), k1<=k<=k2 -rnext k1[,k2] r=nextprime^k(q), k1<=k<=k2 -qmod [+/-]m[,k1[,k2]] q==+/-m (mod p), q=kp+/-m, k1<=k<=k2 -rmod [+/-]m[,k1[,k2]] r==+/-m (mod pq), q=kpq+/-m, k1<=k<=k2 -oneq find one q for each p -oner find one r for each pq -highest output only if the maximum value of height grows -n nice -nn very nice -v verbose -vv very verbose -test x test cyclotomic polynomial by using x^n-1 phipqr -flat 1 -p 1,110 -qnext 1,10 -r 1,50000 -rmod 1 -oneq -v all coefficients satisfy abs(c)<=1 1<=p<=110, q=nextprime^k(p) [1<=k<=10], 1<=r<=50000, r==+/-1 (mod pq) one q for each p n = 2*3*5 = 30 [q=p+1, r=pq-1] n = 3*5*29 = 435 [q=2p-1, r=2pq-1] n = 5*7*71 = 2485 [q=p+2, r=2pq+1] n = 7*11*307 = 23639 [q=2p-3, r=4pq-1] n = 11*13*571 = 81653 [q=p+2, r=4pq-1] n = 13*17*443 = 97903 [q=p+4, r=2pq+1] n = 17*19*647 = 208981 [q=p+2, r=2pq+1] n = 19*23*1747 = 763439 [q=p+4, r=4pq-1] n = 23*29*4001 = 2668667 [q=p+6, r=6pq-1] n = 29*31*5393 = 4848307 [q=p+2, r=6pq-1] n = 31*37*2293 = 2630071 [q=p+6, r=2pq-1] n = 37*41*6067 = 9203639 [q=p+4, r=4pq-1] n = 41*43*3527 = 6218101 [q=p+2, r=2pq+1] n = 43*47*24251 = 49011271 [q=p+4, r=12pq-1] n = 47*53*14947 = 37232977 [q=p+6, r=6pq+1] n = 53*59*31271 = 97784417 [q=p+6, r=10pq+1] n = 59*61*28793 = 103626007 [q=p+2, r=8pq+1] n = 61*67*16349 = 66818363 [q=p+6, r=4pq+1] n = 67*71*28541 = 135769537 [q=p+4, r=6pq-1] n = 71*73*20731 = 107448773 [q=p+2, r=4pq-1] n = 73*79*34603 = 199555501 [q=p+6, r=6pq+1] n = 79*83*26227 = 171970439 [q=p+4, r=4pq-1] n = 83*97*16103 = 129645253 [q=p+14, r=2pq+1] n = 89*101*17977 = 161595253 [q=p+12, r=2pq-1] n = 97*107*20759 = 215457661 [q=p+10, r=2pq+1] n = 101*103*20807 = 216455221 [q=p+2, r=2pq+1] n = 103*109*22453 = 252079831 [q=p+6, r=2pq-1] n = 107*109*23327 = 272062801 [q=p+2, r=2pq+1] cannot allocate 1631291044 bytes at phipqr.c line 390 cannot allocate 1784136100 bytes at phipqr.c line 390 cannot allocate 2167256324 bytes at phipqr.c line 390 cannot allocate 2525402468 bytes at phipqr.c line 390 44.460 sec. phipqr -flat 1 -p 1,110 -qmod +1,2 -r 1,50000 -rmod 2 -oneq -v all coefficients satisfy abs(c)<=1 1<=p<=110, q=2p+1, 1<=r<=50000, r==+/-2 (mod pq) one q for each p n = 3*7*19 = 399 [q=2p+1, r=pq-2] n = 5*11*53 = 2915 [q=2p+1, r=pq-2] n = 11*23*251 = 63503 [q=2p+1, r=pq-2] n = 23*47*5407 = 5844967 [q=2p+1, r=5pq+2] n = 29*59*1709 = 2924099 [q=2p+1, r=pq-2] n = 41*83*10211 = 34748033 [q=2p+1, r=3pq+2] n = 53*107*5669 = 32148899 [q=2p+1, r=pq-2] n = 83*167*13859 = 192099599 [q=2p+1, r=pq-2] cannot allocate 3045625924 bytes at phipqr.c line 390 5.163 sec. phipqr -high 1 -p 277 -q 281 -r 331 n = 277*281*331 = 25764047 [height=86] 0.531 sec. phipqr -high 1 -p 3 -q 5 -r 7 -vv at least one coefficient satisfies abs(c)>=1 p=3, q=5, r=7 n = 3*5*7 = 105 [height=2] Phi_105(x) = x^48+x^47+x^46-x^43-x^42-2*x^41-x^40-x^39+x^36+x^35+x^34+x^33+x^32+x^31-x^28-x^26-x^24-x^22-x^20+x^17+x^16+x^15+x^14+x^13+x^12-x^9-x^8-2*x^7-x^6-x^5+x^2+x+1 0.000 sec. Makoto Kamada Phil Carmody May 12, 2009 ----------------------- --- On Tue, 5/12/09, David Broadhurst wrote: > "David Broadhurst" wrote: > > Conjecture 3 [Broadhurst]: > > If [p,q,r] is a triplet of odd primes > > with q > p and r = +/- 2 mod p*q, > > then Phi(p*q*r) is flat if and only if q = 1 mod p. > > > > Flat examples: [13, 79, 3079], [13, 79, 3083], [13, 157, 2039]. > > Conjecture 4 [Sufficient congruences for flatness]: > Let [p,q,r] be a triplet of primes with r > q > p > > 2. > Let w be the smallest positive integer such that > r = +/- w mod p*q. If both of the congruences > p = 1 mod w ... (1) > q = 1 mod w*p ... (2) > hold, then I conjecture that Phi(p*q*r) is flat. > > Nota Bene: The congruences are not necessary, since [3, 7, 11], > with w = 10, is flat. The second congruence is not necessary > when w = 1. I conjecture that it is necessary and sufficient > when w = 2. So this doesn't completely supplant Conjecture 3 then. However, it looks like progress. The numerical neatness implies that there must be a proof not too far off. (morally) > Tests: Kaplan proved that, for any given p and q, the height > of Phi(p*q*r) is determined by w. Thus flatness of [p, q, r] > may be established by finding the smallest prime, s, with > s = +/- r mod p*q and showing that [p, q, s] is flat. > Thanks to this simplification, I have shown that any > counterexample to Conjecture 4 must have p*q*r > > 25*10^6. Nice work! I'm really glad I posed the question here now! So there are now 3 distinct immediate targets 1) prove/disprove (generalisation of) conjecture 3 2) prove/disprove conjecture 4 3) categorise flatphis which don't fall into Kaplan+/-1 or Broadhurst+/-w Phil Makoto Kamada May 14, 2009 ----------------------- Known story: If p,q,r are distinct prime numbers and p Thus, maximum absolute value of Phi_pqr(x) is not greater than 2p((p-1)(q-1)+1). Thus, maximum absolute value of coefficients of Phi_pqr(x) is not greater than 2p((p-1)(q-1)+1). Makoto Kamada David Broadhurst May 14, 2009 ----------------------- --- In primenumbers@yahoogroups.com, Makoto Kamada wrote: > maximum absolute value of coefficients of Phi_pqr(x) > is not greater than 2p((p-1)(q-1)+1). It was proven more than 100 years ago [1] that the height is less than the smallest prime, p. [1] A.S. Bang, Tidsskr. Math., 6 (1895), 6-12, cited in MR2201603 (2006j:11032) Bachman, Gennady(1-NVLV) Flat cyclotomic polynomials of order three. (English summary) Bull. London Math. Soc. 38 (2006), no. 1, 53--60. 11C08 (11B83) Best regards David Makoto Kamada May 15, 2009 ----------------------- Thank you for your comment. I found the following website. http://www.cecm.sfu.ca/~ada26/cyclotomic/ Makoto Kamada Makoto Kamada May 15, 2009 ----------------------- On 2009/05/15 14:29, David Broadhurst wrote: > --- In primenumbers@yahoogroups.com, > Makoto Kamada wrote: > >> maximum absolute value of coefficients of Phi_pqr(x) >> is not greater than 2p((p-1)(q-1)+1). > > It was proven more than 100 years ago [1] that the > height is less than the smallest prime, p. If maximum absolute value of coefficients of Phi_pqr(x) are less than p, the size necessary for each coefficient is one byte at p<128. phipqr.c was updated. http://homepage2.nifty.com/m_kamada/math/phipqr.c.txt I feel my results are too fast than David's results. Did I make big mistakes? phipqr -flat 1 -p 1,128 -qnext 1,10 -r 1,40000 -rmod 1 -oneq -v all coefficients satisfy abs(c)<=1 1<=p<=128, q=nextprime^k(p) [1<=k<=10], 1<=r<=40000, r==+/-1 (mod pq) one q for each p n = 2*3*5 = 30 [q=p+1, r=pq-1] n = 3*5*29 = 435 [q=2p-1, r=2pq-1] n = 5*7*71 = 2485 [q=p+2, r=2pq+1] n = 7*11*307 = 23639 [q=2p-3, r=4pq-1] n = 11*13*571 = 81653 [q=p+2, r=4pq-1] n = 13*17*443 = 97903 [q=p+4, r=2pq+1] n = 17*19*647 = 208981 [q=p+2, r=2pq+1] n = 19*23*1747 = 763439 [q=p+4, r=4pq-1] n = 23*29*4001 = 2668667 [q=p+6, r=6pq-1] n = 29*31*5393 = 4848307 [q=p+2, r=6pq-1] n = 31*37*2293 = 2630071 [q=p+6, r=2pq-1] n = 37*41*6067 = 9203639 [q=p+4, r=4pq-1] n = 41*43*3527 = 6218101 [q=p+2, r=2pq+1] n = 43*47*24251 = 49011271 [q=p+4, r=12pq-1] n = 47*53*14947 = 37232977 [q=p+6, r=6pq+1] n = 53*59*31271 = 97784417 [q=p+6, r=10pq+1] n = 59*61*28793 = 103626007 [q=p+2, r=8pq+1] n = 61*67*16349 = 66818363 [q=p+6, r=4pq+1] n = 67*71*28541 = 135769537 [q=p+4, r=6pq-1] n = 71*73*20731 = 107448773 [q=p+2, r=4pq-1] n = 73*79*34603 = 199555501 [q=p+6, r=6pq+1] n = 79*83*26227 = 171970439 [q=p+4, r=4pq-1] n = 83*97*16103 = 129645253 [q=p+14, r=2pq+1] n = 89*101*17977 = 161595253 [q=p+12, r=2pq-1] n = 97*107*20759 = 215457661 [q=p+10, r=2pq+1] n = 101*103*20807 = 216455221 [q=p+2, r=2pq+1] n = 103*109*22453 = 252079831 [q=p+6, r=2pq-1] n = 107*109*23327 = 272062801 [q=p+2, r=2pq+1] n = 109*131*28559 = 407793961 [q=p+22, r=2pq+1] n = 113*127*28703 = 411916753 [q=p+14, r=2pq+1] n = 127*149*37847 = 716178781 [q=p+22, r=2pq+1] 35.084 sec. phipqr -flat 1 -p 1,128 -qmod +1,2 -r 1,40000 -rmod 2 -oneq -v all coefficients satisfy abs(c)<=1 1<=p<=128, q=2p+1, 1<=r<=40000, r==+/-2 (mod pq) one q for each p n = 3*7*19 = 399 [q=2p+1, r=pq-2] n = 5*11*53 = 2915 [q=2p+1, r=pq-2] n = 11*23*251 = 63503 [q=2p+1, r=pq-2] n = 23*47*5407 = 5844967 [q=2p+1, r=5pq+2] n = 29*59*1709 = 2924099 [q=2p+1, r=pq-2] n = 41*83*10211 = 34748033 [q=2p+1, r=3pq+2] n = 53*107*5669 = 32148899 [q=2p+1, r=pq-2] n = 83*167*13859 = 192099599 [q=2p+1, r=pq-2] 2.340 sec. phipqr -high 1 -p 277 -q 281 -r 331 n = 277*281*331 = 25764047 [height=86] 0.342 sec. Makoto Kamada David Broadhurst May 15, 2009 ----------------------- --- In primenumbers@yahoogroups.com, Makoto Kamada wrote: > I feel my results are too fast than David's results. Dear Makoto Kamada I am not yet able to compile your wonderful code, since I currently lack the required libraries. Might you provide a linux static executable via the web? > Did I make big mistakes? I did not yet see any mistake in your very impressive postings. With very best regards David (slower than you by a huge factor) David Broadhurst May 15, 2009 ----------------------- Conjectures for flat ternary cyclotomic polynomials Definitions: For a triple T = [p, q, r] of primes with r > q > p > 2, I shall define the height of T as the height of the cyclotomic polynomial Phi(n,x) with n = p*q*r and say that T is flat if it has unit height. Let w be the smallest positive integer such that r = +/- w mod p*q. Then I shall call w the residue of T and shall say that: 1) T is of type 1 if and only if w = 1; 2) T is of type 2 if and only if w > 1, w*p divides q - 1 and w divides p - 1; 3) T is of type 3 if and only if w > p, q > p^2 - p, p divides q^2 - 1, p divides w^2 - 1 and when p divides w - 1 neither q + 1 nor q - 1 is divisible by w*p. Comment: In Journal of Number Theory, 127 (2007), 118–126, Nathan Kaplan proved that for fixed p and q the residue w determines the height of Phi(p*q*r,x) and that w = 1, as in type 1, yields a flat polynomial. Conjecture A [Necessary and sufficient conditions for flatness]: I conjecture that T = [p, q, r] is flat if and only if T is of type 1 or 2, or T is of type 3 and P(x^s)/P(x) is flat, where P(x) = Phi(p*q,x) and s is the smallest positive integer such that s = 1 mod p and s = +/- r mod p*q. Comment: If this be true, then the problem of determining flatness is greatly simplified, at large p, since the fraction of cases that are of type 3 is O(1/p^2). Moreover, if r > p*q, then the degree of P(x^s)/P(x) in the simplified test for type 3 is a fraction (s - 1)/(r - 1) < 1 of the degree of Phi(p*q*r,x), since s < p*q, by definition. The prime r may, occasionally, be less than the test integer s, but only when r = -1 mod p and 2*r < p*q. If so, one may test P(x^r)/P(x), since this coincides with Phi(p*q*r,x) when r is prime. Conjecture B [Bounds for flat cases of type 3]: Let [p, q] be a prime pair with p > 2, q > p^2 - p and q^2 = 1 mod p. Then I conjecture that the number N(p,q) of flat triples [p, q, r] of type 3 with distinct residues is greater than zero and less than B(p,q) = 2*(q - 1)/(p^2 - p). Comment: If this be true, then the probability that Phi(p*q*r,x) is of type 3 and flat is O(1/p^4), since only a fraction 2/(p - 1) of the residues of q modulo p is allowed. Then the fraction of the residues of r modulo p*q that lead to flatness is less than 2*B(p,q)/((p - 1)*(q - 1)). Hence a fraction less than 8/(p*(p - 1)^3) of the residues for [q, r] pairs conjecturally gives flat cases of type 3. Flat examples: In the following examples (and in many others) I tested these conjectures by exhaustion of prime witnesses. With p = 11, q = 131 and prime r > 131, there are (p - 1)*(q - 1)/2 = 650 possible residues w for a triple [11, 131, r]. For each w, I found the smallest prime r > 131 that gives this residue and proved that Phi(11*131*r,x) is indeed flat in all and only those cases asserted by Conjecture A, namely for [11, 131, 8647], with w = 1, of type 1, [11, 131, 1321], with w = 120, of type 3, [11, 131, 4049], with w = 274, of type 3, in agreement with Conjecture B, since 2 = N(11,131) < B(11,131) = 26/11. With p = 11 and q = 109, there are no cases of type 2, since 109 = - 1 mod 11. There are no cases of type 3, since 109 < 11^2 - 11. Thus Conjecture A claims that the sole residue giving a flat triple is w = 1, for [11, 109, 2399]. I confirmed this by exhaustion of 540 prime witnesses. With p = 5 and q = 61, I proved that [5, 61, 1831], with w = 1, of type 1, [5, 61, 307], with w = 2, of type 2, [5, 61, 911], with w = 4, of type 2, [5, 61, 271], with w = 34, of type 3, [5, 61, 229], with w = 76, of type 3, [5, 61, 109], with w = 109, of type 3, [5, 61, 421], with w = 116, of type 3, [5, 61, 439], with w = 134, of type 3, exhaust the residues of flat triples, in agreement with the conjectures, Note that 5 = N(5,61) < B(5,61) = 6. Table: I claim that there are precisely 36919 flat triples [p, q, r] with n = p*q*r < 2116150 = 3*7*100769 + 1, namely those whose n values are tabulated here: http://physics.open.ac.uk/~dbroadhu/cert/hpcflat.txt Counterexamples to my conjectures would be much appreciated. I thank Phil Carmody for prompting this present investigation. David Broadhurst, 15 May 2009 D.Broadhurst May 15, 2009 ----------------------- Makoto Kamada [mailto:m_kamada@...] wrote > I found the following website. > http://www.cecm.sfu.ca/~ada26/cyclotomic/ It turns out that I have used precisely Algorithm 4, of Arnold and Monagan, in http://www.cecm.sfu.ca/~ada26/cyclotomic/CalcCycloPolys.pdf since the ternary case is indeed sparse. I also used this method for Phi(p*q,x^s)/Phi(p*q,x) where s need not be prime, as in my recent conjectures. Thank you for confirming that my method was sensible. David David --------------------------------- The Open University is incorporated by Royal Charter (RC 000391), an exempt charity in England & Wales and a charity registered in Scotland (SC 038302). Makoto Kamada May 15, 2009 ----------------------- On 2009/05/16 0:32, David Broadhurst wrote: > I am not yet able to compile your wonderful code, > since I currently lack the required libraries. > Might you provide a linux static executable via the web? I cannot make a linux static executable because I have no linux box, sorry. Please try new phipqr.c. http://homepage2.nifty.com/m_kamada/math/phipqr.c.txt command line gcc -std=c99 -pedantic -Wall -O3 -o phipqr phipqr.c I'm using gcc version 3. gcc version 4 was installed but it does not work properly. If your compiler does not accept "-std=c99", I will remove all c99 codes. My execution environment is AMD Athlon Dual Core Processor 4850e 2.5GHz, 2GB RAM, Windows Vista Home Basic (32bits) and Cygwin. older versions are http://homepage2.nifty.com/m_kamada/math/phipqr20090512.c.txt http://homepage2.nifty.com/m_kamada/math/phipqr20090515.c.txt Thank you. Makoto Kamada David Broadhurst May 15, 2009 ----------------------- --- In primenumbers@yahoogroups.com, Makoto Kamada wrote: > Please try new phipqr.c. > http://homepage2.nifty.com/m_kamada/math/phipqr.c.txt > command line > gcc -std=c99 -pedantic -Wall -O3 -o phipqr phipqr.c That compiled just fine, thanks! My previous problem was with your recommended flag: -lgmp which crashed compliation. It seemed to me that we do not need GMP at these sizes, as you now confirm. Big thanks! David David Broadhurst May 15, 2009 ----------------------- --- In primenumbers@yahoogroups.com, "David Broadhurst" wrote: > That compiled just fine, thanks! Kamada San writes amazingly fast code: phipqr -flat 1 -p 1,128 -qnext 1,10 -r 1,40000 -rmod 1 -oneq -v all coefficients satisfy abs(c)<=1 1<=p<=128, q=nextprime^k(p) [1<=k<=10], 1<=r<=40000, r==+/-1 (mod pq) one q for each p n = 2*3*5 = 30 [q=p+1, r=pq-1] .... n = 127*149*37847 = 716178781 [q=p+22, r=2pq+1] 55.440 sec. If I had this tool a few days ago, life might have been much simpler? But then again, perhaps not, since it was precisely the slowness of my Pari-GP code that led me to seek for integer surrogates and hence to formulate my conjectures. David David Broadhurst May 15, 2009 ----------------------- --- In primenumbers@yahoogroups.com, "David Broadhurst" wrote: > Definitions: For a triple T = [p, q, r] of primes with > r > q > p > 2, I shall define the height of T as the height > of the cyclotomic polynomial Phi(n,x) with n = p*q*r and > say that T is flat if it has unit height. Let w be the > smallest positive integer such that r = +/- w mod p*q. > Then I shall call w the residue of T and shall say that: > 1) T is of type 1 if and only if w = 1; > 2) T is of type 2 if and only if w > 1, > w*p divides q - 1 and w divides p - 1; > 3) T is of type 3 if and only if w > p, q > p^2 - p, > p divides q^2 - 1, p divides w^2 - 1 and when > p divides w - 1 neither q + 1 nor q - 1 is divisible by w*p. > Conjecture A [Necessary and sufficient conditions for flatness]: > I conjecture that T = [p, q, r] is flat if and only if > T is of type 1 or 2, or T is of type 3 and P(x^s)/P(x) is flat, > where P(x) = Phi(p*q,x) and s is the smallest positive integer > such that s = 1 mod p and s = +/- r mod p*q. > Conjecture B [Bounds for flat cases of type 3]: > Let [p, q] be a prime pair with p > 2, q > p^2 - p and > q^2 = 1 mod p. Then I conjecture that the number N(p,q) of > flat triples [p, q, r] of type 3 with distinct residues is > greater than zero and less than B(p,q) = 2*(q - 1)/(p^2 - p). Tony Noe has told me that his OEIS sequences on this topic will soon become visible. Reminder: > Counterexamples to my conjectures would be much appreciated. David Makoto Kamada May 15, 2009 ----------------------- On 2009/05/16 3:27, David Broadhurst wrote: > My previous problem was with your recommended flag: -lgmp > which crashed compliation. It seemed to me that we do not > need GMP at these sizes, as you now confirm. I removed gmp codes yesterday but I forgot to remove "-lgmp" from the comment line. I'm sorry for confusing you. Multiple precision arithmetics is not needed to calculate cyclotomic polynomials if the final coefficients are small enough to fit in a register. Makoto Kamada Makoto Kamada May 15, 2009 ----------------------- On 2009/05/16 3:58, David Broadhurst wrote: > But then again, perhaps not, since it was precisely the > slowness of my Pari-GP code that led me to seek for integer > surrogates and hence to formulate my conjectures. I think I understand what you mean. However, mathematics is difficult for me whether my program is fast or not! Makoto Kamada djbroadhurst May 23, 2013 ----------------------- --- In primenumbers@yahoogroups.com, "David Broadhurst" wrote: > Conjectures for flat ternary cyclotomic polynomials Sam Elder, at MIT, has made impressive progress http://arxiv.org/abs/1207.5811 on this subject, which Phil Carmody and I studied on this list, with algorithmic help from Makoto Kamada. Sam's article references this list: [4] D. Broadhurst, Cyclotomic polynomials puzzles, Yahoo Groups primenumbers message #20282, http://tech.groups.yahoo.com/group/primenumbers/message/20282 [5] D. Broadhurst, Flat ternary cyclotomic polynomials, Yahoo Groups primenumbers message #20305, http://tech.groups.yahoo.com/group/primenumbers/message/20305 but it is also important to record, here, the interaction with Phil and Makoto, on this list, that informed my work. Sometimes, maths authors are reluctant to reference our amateur musings, in PrimeNumbers. Sam took the opposite view. David (never a proper mathematician) yasep16 May 23, 2013 ----------------------- Le 2013-05-23 15:47, djbroadhurst a écrit : > David (never a proper mathematician) What's a "proper mathematician" ? djbroadhurst Message 43 of 43 , May 23, 2013 ----------------------- --- In primenumbers@yahoogroups.com, whygee@... asked: > What's a "proper mathematician" ? On who regularly publishes, in mathematical journals, articles that do not derive principally from other subjects, such as physics. David (pleading not guilty)