Analogy of A018805 for the ring GF(2)[x]

[Edwin Clark]

I want to make a correction to my previous posting concerning the number
of ordered k-tuples (f_1, ..., f_k) of polynomials in GF(q)[x] such that
gcd((f_1, ..., f_k) = 1 with various restrictions on the degrees.

Originally the paper by Stephen Suen, David des Jardin and me was couched
in terms of probabilities that gcd((f_1, ..., f_k) = 1 and when
translating to the number of such polynomials I made a mistake. Rather
than just point that out I will restate what hopefully is correct:
(The mistake involved case 3 below.)

There are three restrictions on degrees that we considered:

1. 1 <= deg(f_i) <= n for all i.

2. deg(f_i) <= n for all i.

3. Given any sequence of positive integers n_1,...,n_k require that
deg(f_i) = n_i.

In terms of probabilities we found the following corresponding formulas:

p1. 1-1/q^(k-1)

p2. 1 - 1/q^(k-1) + (q-1)/q^((n+1)*k)

p3. 1-1/q^(k-1)  [Yes! The same as p1.]

The number of k-tuples of polynomials with gcd = 1 satisfying the various
conditions can be obtained easily from these probabilites: They are
respectively:

n1. (q^(n+1)-q)^k*(1-1/(q^(k-1)))

n2. q^((n+1)*k) * (1 - 1/q^(k-1) + (q-1)/q^((n+1)*k))

n3. (q-1)^k*q^(n_1+...+n_k)*(1-1/(q^(k-1)))

I plan to submit sequences n1 and n2 for several small values of k and q
to the OEIS or add comments if they already exits if someone hasn't beat
me to it.


Edwin


On Thu, 28 Aug 2003, Edwin Clark wrote:
> 
> 
> I don't know if it's in the OEIS. However, in 1997 Stephen Suen, David
> des Jardin and I wrote a paper (which we never got around to
> publishing) in which we proved that for n > 0 and k > 1 the number of
> k-tuples of polynomials (f_1, f_2, . . . , f_k) in GF(q)[x] each of degree
> from 1 to n such that gcd(f_1, f_2, . . . , f_k) = 1 is exactly 
> 
>        (q^(n+1)-q)^k*(1-1/(q^(k-1)))
> 
> It is a curious fact that for fixed positive integers n_i, i=1..k, the
> number of k-tuples of polynomials (f_1, f_2, . . . , f_k) in GF(q)[x] with
> deg(f_i) = n_i and gcd(f_1, . . . , f_k) = 1 is given by the same
> formula!. 
> 
> We also calculated the number of k-tuples of polynomials (f_1, . . .,
> f_k) where deg(f_i) <= n and gcd(f_1,...,f_k) = 1 to be:
> 
>    q^((n+1)*k) * (1 - 1/q^(k-1) + (q-1)/q^((n+1)*k))
> 
> I still have a copy of the paper if you'd like a copy. However, I think
> that  knowing the answer makes it easy enough to prove these facts.
> 
> --Edwin
> 
> 
> 
> 
> 
> 

------------------------------------------------------------
    W. Edwin Clark, Math Dept, University of South Florida,
           http://www.math.usf.edu/~eclark/
------------------------------------------------------------