Analogy of A018805 for the ring GF(2)[x]
Edwin Clark
eclark at math.usf.edu
Fri Aug 29 12:24:05 CEST 2003
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/
------------------------------------------------------------
More information about the SeqFan
mailing list