Probability of coprime polynomials Given positive integer $N$, we choose $m_1, m_2, n_1, n_2$ independently and with equal probabilities from $\{0,1,\ldots,N\}$, and let 
$f_1 = x^{m_1} + (1+x)^{n_1}$ and $f_2 = x^{m_2} + (1+x)^{n_2}$ as polynomials in the indeterminate $x$ over the field ${\mathbb F}_2$ of two elements.  Let $P(N)$ be the probability  that $f_1$ and $f_2$ are coprime.  What can be said about $P(N)$, in particular its asymptotics as $N \to \infty$?
By explicit enumeration in Maple, the first few values are
$$\eqalign{P \left( 1 \right) &={\frac {9}{16}},P \left( 2 \right) ={\frac {56}{
81}},P \left( 3 \right) ={\frac {45}{64}},P \left( 4 \right) ={\frac {
489}{625}},P \left( 5 \right) ={\frac {1019}{1296}},\cr P \left( 6
 \right) &={\frac {1895}{2401}},P \left( 7 \right) ={\frac {3299}{4096}
},P \left( 8 \right) ={\frac {5308}{6561}},P \left( 9 \right) ={\frac 
{2023}{2500}},P(10) = \frac{11954}{14641}\cr}$$ 
Random sampling seems to indicate $P(100) \approx 0.83$. The sequence $(N+1)^4 P(N)$
does not appear to be in the OEIS.  
EDIT: That sequence is now in the OEIS as A245488.
$P(100) = 86648767/101^4 \approx 0.8326776196$.
 A: This seems to be a hard and interesting problem.  Here's a heuristic on the correct answer, but I have little hope that it can be made into a proof.  Below let $D$ denote a polynomial in ${\Bbb F}_2[x]$ and let $\mu(D)$ denote the Mobius function.  We will only be interested in $D$ that are coprime to $x(1+x)$.  For such $D$ consider the group generated by $x$ and $1+x$ in $({\Bbb F}_2[x]/D)^*$; denote this by $\langle x,1+x\rangle_D$ and its order by 
$|\langle x,1+x\rangle_D|$.  The conjectured probability is 
$$ 
\sum_{D, (D,x(1+x))=1} \frac{\mu(D)}{|\langle x, 1+x \rangle_D|^2}. 
$$ 
To see why this is, note that we can identify whether  $(f,g)=1$ by summing $\sum_{D|f, D|g} \mu(D)$.  Thus the problem asks for 
$$ 
\sum_{D, (D,x(1+x))=1} \mu(D) \Big( \frac{1}{(N+1)^2} \sum_{0 \le a, b\le N; D|x^a+(1+x)^b} 1\Big)^2. 
$$ 
The probability that $D$ divides $x^a+(1+x)^b$ is the same as the probability that 
$D$ divides $x^m (1+x)^n +1 = x^m (1+x)^n -1$.  Since $x^m (1+x)^n$ ranges uniformly over the elements of $\langle x,1+x \rangle_D$, this probability is clearly $1/|\langle x,1+x\rangle_D|$.  This justifies heuristically the conjecture.  The argument could be made precise by splitting $a$ and $b$ into intervals of size the order of $x$ in $({\Bbb F}_2[x]/D)^*$ and the order of $1+x$ there.  The trouble is that there will be an error of 
size $O(1/N)$ in doing so, and this cannot be controlled as the sum over $D$ includes exponentially many terms.   
It seems plausible that the sum over $D$ in the conjecture converges, but I don't see any way to prove this.  It would be interesting to compute it numerically. One can get something rigorous by doing the above analysis with only those $D$ whose irreducible factors have degree below $\log N$ say.  In this way one obtains an upper bound for the desired probability.   
A: The probability that two random polynomials of large degree in F_2[t] are coprime is $\zeta(2)^{-1}$, or 1/2.  Your polynomials are not quite random; neither one is divisible by x or x+1.  The probability that two polynomials, both prime to x(x+1), are coprime, is obtained by removing the two corresponding local factors of the Euler product for $\zeta(2)$; in other words, without that restriction, there would be a common factor of x 1/4 of the time, and a common factor of (1+x) 1/4 of the time.  So the probability that two polynomials, both coprime to x(x+1), are coprime to each other is (4/3)(4/3)(1/2) = 8/9.  This is not quite what you get.  What happens when you try it with the variables ranging from 1 to N instead of 0 to N?
Update: Mike Zieve's answer is better than mine, so am I supposed to downvote mine, or what?
A: (Edited in response to Julian Rosen's comments)
As $N\to\infty$, one could guess that $P(N)$ approaches
$$
\prod_{p} \Bigl(1 - \Bigl(\frac{\gcd(a_p,b_p)}{a_p b_p}\Bigr)^2\Bigr),
$$
where the product is over all irreducibles $p(x)\in\mathbf{F}_2[x]$ of degree at least $2$, and $a_p$ and $b_p$ denote the orders of $x$ and $x+1$ in the multiplicative group of $\mathbf{F}_2[x]/(f(x))$, respectively.  This is because this group is cyclic, so the intersection of subgroups of orders $a_p$ and $b_p$ has order $\gcd(a_p,b_p)$.  Then the number of pairs $(m,n)$ with $1\le m\le a_p$ and $1\le n\le b_p$ for which $p\mid x^m+(1+x)^n$ is $\gcd(a_p,b_p)$, so if $N$ is large compared to $a_p$ and $b_p$ then the proportion of the pairs $(m,n)$ with $0\le m,n\le N$ for which $p\mid x^m+(1+x)^n$ will approach $\gcd(a_p,b_p)/(a_pb_p)$.  Hence the probability that $p$ divides both $x^{m_1}+(1+x)^{n_1}$ and $x^{m_2}+(1+x)^{n_2}$ approaches the square of $\gcd(a_p,b_p)/(a_pb_p)$, which yields the claimed formula.
However, as Julian Rosen points out, I'm implicitly assuming the independence of divisibility by distinct primes $p$, which isn't valid.  So my formula should be modified somehow.  On the other hand, I computed the displayed product over $p$'s of degree up to $15$, and got $0.8321...$, matching Robert Israel's computations.  So maybe my formula is a reasonable approximation to the truth.
