mersenneforum.org > Math New cyclotomic factorisations?
 Register FAQ Search Today's Posts Mark Forums Read

 2023-04-29, 12:36 #1 Andrew Usher   Dec 2022 24×33 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.
 2023-05-01, 10:56 #2 Drdmitry     Nov 2011 23×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
 2023-05-02, 12:33 #3 Andrew Usher   Dec 2022 24×33 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.
 2023-05-08, 03:32 #4 Andrew Usher   Dec 2022 24×33 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 non-paywalled 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.
 2023-05-08, 10:57 #5 charybdis     Apr 2020 22·3·5·17 Posts FYI Drdmitry is the author of the paper.
 2023-05-09, 23:15 #6 Andrew Usher   Dec 2022 24·33 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).
 2023-05-15, 14:50 #7 Dr Sardonicus     Feb 2017 Nowhere 32×709 Posts See also, e.g. this post in this thread.
 2023-05-17, 15:48 #8 chris2be8     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)/90-1)/3946751904+1)/1221828-1)/30-1)/1439676372+1)/4+1)/23994+1)/234-1)/20+1)/1848-1)/15227632858125752880-1)/25220-1)/2-1)/225100232050 There are quite a lot like the last number, but I doubt they can be factored.
 2023-05-18, 12:18 #9 Andrew Usher   Dec 2022 24×33 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^5-t, ... (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^2-1'. 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 already-known 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!
2023-05-18, 13:15   #10
Dr Sardonicus

Feb 2017
Nowhere

32·709 Posts

Quote:
 Originally Posted by Andrew Usher Dr. Sardonicus: That other thread, as you yourself admit there, only obtains the already-known 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!
You did note the title of the paper, didn't you? If you'd bothered reading the post you refer to, you would also have realized that contrary to your proclamation, the formula is not merely "theoretically interesting," it is computationally much faster than the traditional method of finding the coefficients of the Aurifeuillian polynomial factors (my emphasis):
Quote:
 Originally Posted by Dr Sardonicus The factors are the same, but the gcd formula in the "Chinese paper" gives a new way to compute them. Some years back I computed an Aurifeuillian factorization using the formula given in an earlier paper (it computed the usual polynomial factors IIRC), then by using the formula in the "Chinese paper." The "Chinese paper" formula was ten times faster.
EDIT: I sudenly remembered, there are also essentially cyclotomic factorizations in this thread of sums and differences of Fibonacci numbers and of Lucas numbers whose indices differ by an even number.

Last fiddled with by Dr Sardonicus on 2023-05-19 at 12:43

 2023-05-20, 12:26 #11 Andrew Usher   Dec 2022 24·33 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).

 Similar Threads Thread Thread Starter Forum Replies Last Post MisterBitcoin MisterBitcoin 0 2018-07-24 15:50 Batalov And now for something completely different 0 2016-06-21 21:02 mickfrancis Factoring 2 2015-01-11 18:31 plandon Math 22 2009-07-29 18:59 wpolly Programming 1 2009-01-23 22:08

All times are UTC. The time now is 04:02.

Sun May 28 04:02:24 UTC 2023 up 283 days, 1:30, 0 users, load averages: 1.00, 0.97, 0.93