New cyclotomic factorisations?

Andrew Usher · 2023-04-29, 12:36

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.

Drdmitry · 2023-05-01, 10:56

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

Andrew Usher · 2023-05-02, 12:33

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.

Andrew Usher · 2023-05-08, 03:32

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.

charybdis · 2023-05-08, 10:57

FYI Drdmitry is the author of the paper.

Andrew Usher · 2023-05-09, 23:15

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).

Dr Sardonicus · 2023-05-15, 14:50

See also, e.g. this post in this thread.

chris2be8 · 2023-05-17, 15:48

@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.

Andrew Usher · 2023-05-18, 12:18

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!

Dr Sardonicus · 2023-05-18, 13:15

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.

Andrew Usher · 2023-05-20, 12:26

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).

2023-04-29, 12:36	#1
Andrew Usher Dec 2022 2⁴×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.

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 kx^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^201096+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.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
My p^11-1 fully factorisations	MisterBitcoin	MisterBitcoin	0	2018-07-24 15:50
Cyclotomic primes (degree>=5)	Batalov	And now for something completely different	0	2016-06-21 21:02
Cyclotomic Polynomial Factoring methods	mickfrancis	Factoring	2	2015-01-11 18:31
Cyclotomic Phi	plandon	Math	22	2009-07-29 18:59
Multiplication in cyclotomic rings	wpolly	Programming	1	2009-01-23 22:08

2023-05-01, 10:56	#2
Drdmitry Nov 2011 2³×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 2⁴×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.

2023-05-08, 03:32	#4
Andrew Usher Dec 2022 2⁴×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 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 2²·3·5·17 Posts	FYI Drdmitry is the author of the paper.

2023-05-09, 23:15	#6
Andrew Usher Dec 2022 2⁴·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).

2023-05-15, 14:50	#7
Dr Sardonicus Feb 2017 Nowhere 3²×709 Posts	See also, e.g. this post in this thread.

2023-05-18, 12:18	#9
Andrew Usher Dec 2022 2⁴×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^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-20, 12:26	#11
Andrew Usher Dec 2022 2⁴·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).