From N to infinity

Algebra Level 5

Let S S be a randomly chosen 6 6 -element subset of the set 0 , 1 , 2 , . . . , n {0, 1, 2, . . . , n} . Consider the polynomial

P ( x ) = i S x i \large\ \displaystyle P( x ) = \sum _{i \in S} { { x }^{ i } } .

Let X n X_n be the probability that P ( x ) P(x) is divisible by some non-constant polynomial Q ( x ) Q(x) of degree at most 3 3 with integer coefficients satisfying Q ( 0 ) 0 Q(0) \neq 0 . Find the limit of X n X_n as n n goes to infinity.


The answer is 0.482976466.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Patrick Corn
Jan 16, 2019

The way I did the problem was to compute the probability that the primitive 2nd, 3rd, 4th, and 6th roots of unity were roots of P P (other than 1 , 1, which cannot be a root of P ( x ) , P(x), these are the only roots of unity whose minimal polynomials have degree 3 \le 3 ). It turned out that the only way a 6th root of unity could be a root of P P was if a 3rd or 2nd root already was, so I could ignore that. The conditions on the exponents for the other three were conditions mod 2,3,4 respectively, so the middle condition was independent of the first and last. The first and last conditions also turned out to be mutually exclusive.

In other words, if p i p_i denoted the probability that a primitive i i th root of unity ( i = 2 , 3 , 4 i = 2,3,4 ) was a root of P , P, then the probability that at least one of them is a root is P 2 + P 3 + P 4 P 2 P 3 P 3 P 4 . P_2 + P_3 + P_4 - P_2P_3 - P_3P_4. It's easy to compute P 2 = 5 / 16 , P_2 = 5/16, P 3 = 10 / 81 , P_3 = 10/81, P 4 = 25 / 256. P_4 = 25/256. (Ok, I cheated and did P 4 P_4 by a computer search of exponents mod 4. 4. But the other two are easy to derive from first principles.)

Anyway, this gives an answer of 10015 / 20736 0.482976466. 10015/20736 \approx 0.482976466. But I have no idea how to prove that if Q ( x ) Q(x) is a cubic polynomial with nonzero constant term and integer coefficients which is not divisible by any of x + 1 , x 2 + x + 1 , x 2 + 1 , x 2 x + 1 , x+1, x^2+x+1, x^2+1, x^2-x+1, then the probability that Q ( x ) Q(x) divides P ( x ) P(x) goes to 0 0 as n . n \to \infty. Does anyone have an explanation?

1 pending report

Vote up reports you agree with

×

Problem Loading...

Note Loading...

Set Loading...