Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If we suppose that we have a polynomial $q(x)$ of the following form:

$q(x) = \sum_{i=0}^N{c_i x^i} \text{ where } c_i=0 \text{ or } c_i=1$

In other words, if we are given a polynomial with binary coefficients (either 0 or 1), what is the probability that $q(x) \bmod p \equiv 0$ where $p$ is prime? There is a twist. We set $x$ equal to 1. That's the probability I'm after. It should be pretty simple.

Now, what I'm really after is a proof that as $N$ tends to infinity, this probability tends to $1/p$ if we set $x=1$.. I'd be delighted if someone could prove this. However, I'd still like to know the probability for any $N$. Additionally, I'm also interested in the cases where we set $x$ equal to a natural less than $p$.

share|improve this question
    
Do you intend $x$ to be a uniformly distributed integer over $[0,p-1]$ ? –  Sasha Oct 5 '11 at 19:20
    
@Sasha: Sorry, I meant a simpler problem. I let $x=1$. Please see the new question. Sorry again for the mistakes. –  Matt Groff Oct 5 '11 at 19:26
    
If you let $x=1$, then you're just looking at $\sum_{i=0}^N c_i$... are you supposing the coefficients $c_i$ to be random? It's not clear in your post where the randomness comes in. –  Bruno Joyal Oct 5 '11 at 19:41
    
@Bruno Joyal: Essentially, yes. You can assume the $c_i$'s are random taken from the set of 0 and 1 (2 elements). Then I'm looking into the limits as $N$ approaches infinity. However, I realized that I also need to know about the cases when $x$ is set equal to a natural less than $p$. –  Matt Groff Oct 5 '11 at 19:45
    
It seems from intuition that all probabilities as $N$ tends to infinity are just $1/p$ that the polynomial is equivalent to 0. I just can't seem to come up with a good way to prove it. –  Matt Groff Oct 5 '11 at 19:54

1 Answer 1

up vote 3 down vote accepted

This is a Markov chain problem. The residue mod p can be any one of p values; as we increment N, we multiply the vector of residue probabilities by a doubly-stochastic matrix with entries 0 and 1/2 which will depend on the value of N and x. This set of matrices will repeat with period equal to the period of x in $(Z/pZ)^*$. The product of the matrices in a single period is also doubly-stochastic, and therefore has a maximal eigenvalue of 1 and an eigenvector $(1,1,\ldots,1)$. In the limit as N gets large, the maximal eigenvalue is the only one which matters, and therefore the probability vector of residues converges to a constant times said eigenvector. Normalizing, we get that g(x) takes on values $[0,\ldots,p-1]$ with probability $1/p$ each in the limit.

share|improve this answer
    
N.B. This matrix is just $1/2 I + 1/2 S^{x^N}$, with $S$ being the cyclic-shift matrix. –  Craig Oct 5 '11 at 20:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.