20230429, 12:36  #1 
Dec 2022
2^{4}×3^{3} Posts 
New cyclotomic factorisations?
The data I have that inspires this is many years old but I have not presented it before. By an algebraic factorisation of a cyclotomic polynomial I mean an identity in one variable that factors a cyclotomic in infinitely many cases.
The only such I have ever seen mentioned are the Aurifeuillian factorisations (yes, they really are underlyingly based on cyclotomic polynomials, though usually not presented in that form) are well known. On Wagstaff's Cunningham page there is a link to a paper implying that no other similar factorisations are known. I don't know, however, what category might be considered similar. I do know that there are other algebraic factorisations I have found, that, unlike those of interest for Cunningham numbers, involve large bases and small exponents; the factors are distinctly unequal and the smaller is another cyclotomic (that's why I found them  my method was manual examination of long tables generated by my computer program, and noticing any 'interesting' factors). Is anything known about this sort? Should infinitely many kinds be expected? I doubt my list is complete and as stated if neither factor were cyclotomic there's no way I would have found them. If no one does I'll have to assume mine are new. For one example I'll give if y = x^5  x we have y^4 + 1 = (x^8  x^4 + 1) (x^12  3x^8 + 2x^4 + 1) and as for all algebraic factorisations the homogeneous case is also possible. 
20230501, 10:56  #2 
Nov 2011
2^{3}×37 Posts 
Hi Andrew,
I am afraid, that factorisation is not new. For example, it can be found in the paper: https://www.worldscientific.com/doi/...93042117500129 but I am pretty sure it was known before. For any irreducible polynomial P(x) one can relatively easily construct another polynomial (and in fact plenty of them) f(x) such that P(f(x)) factors into a product of two polynomials. The advantage of Aurifellian factorisations is that usually they are for big powers and small values x. That makes them useful for numbers like \(b^n\pm 1\). While these polynomial factorisations are usually for small powers and big numbers x. Here is another paper where many factorisations like your one are constructed: https://arxiv.org/abs/1607.07212 
20230502, 12:33  #3 
Dec 2022
2^{4}×3^{3} Posts 
Thank you! The second paper was completely over my head, but the first was more approachable (you posted a paywalled version, but Google Scholar found the free one). It will take some time to properly reply to that, but yes, all my identities fall under that broad category and are 1 modulo the base as well as the exponent.

20230508, 03:32  #4 
Dec 2022
2^{4}×3^{3} Posts 
One easy extension is that the conclusions he drew about x^4 + 1 (the order 8 cyclotomic) apply equally to x^4  x^2 + 1 (the order 12) with only a small change in the recursion.
I supply a link to the nonpaywalled version of the paper: https://dro.dur.ac.uk/17370/1/17370.pdf (I hope that's OK to do). For anyone curious, his first point is sharpening the bound on the _maximum_ power of 2 in Fermat factors from 'less than the cube root' (enough to show F4 prime without calculation) to 'less than the fourth root'  which is sharp, demonstrated by the compositeness of F5. 
20230508, 10:57  #5 
Apr 2020
2^{2}·3·5·17 Posts 
FYI Drdmitry is the author of the paper.

20230509, 23:15  #6 
Dec 2022
2^{4}·3^{3} Posts 
Yes, that was evident. I didn't think it necessary to say so, as I can safely assume he knows that it's his paper! The last post was directed toward any third party that may come across it (and would probably figure it out just as I did, but if not it's no big deal).

20230515, 14:50  #7 
Feb 2017
Nowhere
3^{2}×709 Posts 
See also, e.g. this post in this thread.

20230517, 15:48  #8 
Sep 2009
11×223 Posts 
@Drdmitry, do you have a program or sample code to find factors of k*x^n+/c numbers? I'm running a script that goes through composite numbers in factordb and adds algebraic factors factordb doesn't know of.
I do all cases of x^n+/1 (aided by cyclo from http://myfactors.mooo.com/) and cases based on x^4n+4. Code to find factors of other cases such as those mentioned in your paper would be much appreciated. A few random examples from factordb: Code:
(2^6641+164851)/282543099 (10^2010*96+48241)/7605585604532904186851 (2^6641+165859)/266786301 (14438^482+1)/504187357817065 (((((((((((((((2^6900*1401+1)/202127314336553+1)/901)/3946751904+1)/12218281)/301)/1439676372+1)/4+1)/23994+1)/2341)/20+1)/18481)/152276328581257528801)/252201)/21)/225100232050 
20230518, 12:18  #9 
Dec 2022
2^{4}×3^{3} Posts 
I still don't understand what you're getting at, any more than I did in the other thread. Are you saying there are or should be algebraic factorisations for _general_ numbers of that form?
In plain language, the one he finds in that paper (of which mine is a special case) factors x^4 + 1 when x belongs to a Lucas sequence t, t^3, t^5t, ... (each term is t^2 the last less the one before); and into a chain of algebraic factors where we define the first term to have smaller part 1 and larger part the whole  then the smallest part of each is the larger of the last. The fact that the first relation equals a known algebraic factorisation made it more complicated. Similarly, I just saw that factorisations of x^4  x^2 + 1 will follow the same pattern where 't^2' is replaced by 't^21'. An infinite series I originally spotted allows x^2k  x^k + 1 to take the first step (t > t^(k+1)  t) for all k not 1 mod 3 but for higher k this is not a recurrence and there are no further steps. The remainder of the two on polynomial division is always 0 when k is not 1 mod 3, and 3 when it is. Dr. Sardonicus: That other thread, as you yourself admit there, only obtains the alreadyknown Aurifeuillian factorisations a different way. While it may be theoretically interesting, it is not new factorisations, and in practice the existing methods of their computation are already much faster than factoring! 
20230518, 13:15  #10  
Feb 2017
Nowhere
3^{2}·709 Posts 
Quote:
Quote:
Last fiddled with by Dr Sardonicus on 20230519 at 12:43 

20230520, 12:26  #11 
Dec 2022
2^{4}·3^{3} Posts 
First, to your addition concerning Lucas identities: those are not aurifeuillian, but simple algebraic. They are almost immediate from the Binet formulae, and can be put in the form of a difference (or a sum in the other cases) because Q = 1. I note also that factoring differences for a^n +/ 1 is trivial.
For the 'Chinese paper' as you called it, I of course read the post, the thread, and looked at the paper. I did note the title of the paper, though you have not quoted it, perhaps because it will likely be misleading  as it was to the next poster after you. I understand what they did, and that is why I commented that it's not of much practical importance to compute them faster as this is already quite fast in the interesting cases. Only when (the squarefree part of) the base is very large does it become difficult to find the polynomials, which is just when the numbers are beyond our ability to factor anyway (as the exponent must be at least as large as the base). 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
My p^111 fully factorisations  MisterBitcoin  MisterBitcoin  0  20180724 15:50 
Cyclotomic primes (degree>=5)  Batalov  And now for something completely different  0  20160621 21:02 
Cyclotomic Polynomial Factoring methods  mickfrancis  Factoring  2  20150111 18:31 
Cyclotomic Phi  plandon  Math  22  20090729 18:59 
Multiplication in cyclotomic rings  wpolly  Programming  1  20090123 22:08 