Factorization polynomials

Franklin Lee
leewangzhong@yahoo.com

Proposal: Factorization polynomials. Given a positive integer N with prime factorization (p1^a1)*(p2^a2)*...*(pn^an), construct a polynomial P(N) = ((p1-x)^a1)*((p2-x)^a2)*...((pn-x)^an). Then the roots of this polynomial are exactly the prime factors of the number N. The question: How does the sum of the factor polynomial of two numbers relate to the polynomial of their sum?

Since factorization polynomials, as defined, require us to factor integers, we need a function to factor an integer.

?FactorInteger

FactorInteger[720]

FactorInteger[1]

Clear[x](* Clear the value of x, so that we can use it as a variable in our polynomials. *)

Here I define my three functions: the helper functions polyize and polymult, and the main function P. P will produce the factorization polynomial as we defined above.

(* Polyize: Given a pair {Prime,Exponent}, construct the polynomial (Prime - x)^Exponent. *)
polyize[{a_,b_}]:=(a-x)^b;
polyize[{1,_}]:=1; (* 1 is not actually a prime, but FactorInteger factors the number 1 into 1^1, so we have to make sure it doesn't affect our polynomial function by making polyize[{1,1}] into the multiplicative identity, also known as the empty product. *)

polyize[{4,3}]

(* Given a list of factors with exponents, construct a polynomial out of them. *)
polymult[{a_,b__}]:=polyize[a]*polymult[{b}];
polymult[{a_}]:=polyize[a]

polymult[{{1,4},{2,3},{5,2}}]

(* Take a number and construct its factorization polynomial. *)
P[n_]:=polymult[FactorInteger[n]]

P[1]

P[2]

P[10]

Let's start looking at the patterns.

First, I claim that P[n] evaluated at x=n is 0 if and only if n is prime. We can have Mathematica show us that it is true for the first several integers, and it can be proven that it's true for all positive integers. We use /. to replace x in the polynomial with n, written as "P[n]/.x->n".

?/.

(* Look at P[n] evaluated at n for the first 20 numbers, checking whether or not n is also prime. *)
Table[{n,If[PrimeQ[n],"Prime",""],P[n]/.x->n},{n,1,20}]//TableForm

It would be nice to say that we can quickly tell if a number is prime by finding its factorization polynomial and plugging the number into the polynomial, but that would only work if we didn't already need the factorization of the number to find its factorization polynomial. So if we can find a fast way to get the polynomial from the number, we would have a fast algorithm for determining whether or not a number is prime.

Note that the first fast primality test that didn't rely on unproven hypotheses (such as the famous Riemann hypothesis) was published in 2002. To some people, that would mean that it's probably hard to find a fast way to get factorization polynomials, if it's possible at all. To others, it means that it would be interesting to find a way to quickly find factorization polynomials, and thus it would be interesting to find patterns in factorization polynomials that aren't easy to see.

Another point of note: P[n]P[m] = P[n*m]. In words, the product of factorization polynomials of two numbers is the factorization polynomial of the product of the numbers. This is called multiplicativity.

Now let's see how far away P[n]+P[m] is from P[n+m]. I fix m and generate a table with one column being P[n]+P[m], a second being P[n+m], and a third being their difference divided by x (since the difference will always have x=0 as a root).

m=2;Table[{m, n,Expand[P[n]+P[m]],Expand[P[n+m]],Simplify[Expand[(P[n]+P[m]-P[n+m])]/x]},{n,1,10}]//TableForm

Notice that when m = 2n or 2n = m, the difference in the two polynomials is 0. In other words, they're equal. So Mathematica suggests that P[n]+P[2n]=P[3n]. We can generate a table of values to quickly test the first hundred cases of n.

Table[Expand[P[n]+P[2n]-P[2n+n]],{n,1,100}]

Mathematica suggests yes. Let's prove it.

P[n]+P[2n]	= P[n]+P[2]P[n] (by multiplicativity of the polynomial function)
		= P[n] (1+P[2]) (by distributive law)
		= P[n] (1+(2-x)) (by definition of P[2])
		= P[n] (3-x) (by adding)
		= P[n]P[3] (by definition of P[3])
		= P[3n] (by multiplicativity)

So now we have at least one rule for finding the polynomial of a sum, but the sum must be a multiple of 3, which is useless if we want to check if the sum is a prime.

I'll try to inspect the factorization of the factorization polynomial next. The next table presents the factorization of P[n]+P[m] for m=0, 1, 2, 3, 4, 5 and n=1, 2, ..., 20.

m=2;Prepend[Table[{"n","=",n,Factor[P[n]+P[2]],Factor[P[n]+P[3]],Factor[P[n]+P[4]],Factor[P[n]+P[5]]},{n,1,20}],{"","","","m = 2","m = 3","m = 4","m = 5"}]//TableForm

And four tables comparing P[n+m] with P[n]+P[m]:

m=2;Table[{n, m, n+m,P[n+m], Factor[P[n]+P[m]]},{n,1,20}]//TableForm

m=3;Table[{n, m, n+m,P[n+m], Factor[P[n]+P[m]]},{n,1,20}]//TableForm

m=4;Table[{n, m, n+m,P[n+m], Factor[P[n]+P[m]]},{n,1,20}]//TableForm

m=5;Table[{n, m, n+m,P[n+m], Factor[P[n]+P[m]]},{n,1,20}]//TableForm

Conjectures that I think of after staring at these for a while:
- If n and m are odd primes, then P[n]+P[m] = 2*P[(m+n)/2] (can be proven)
- P[n+m] = P[n]+P[m] only if one is twice the other (unproven)

Neither conjecture would help us find factorization polynomials for potential primes, so I haven't gotten anywhere in terms of finding a fast way to check if a number is prime. However, we have found two rules for the sum of factorization polynomials.