Dear Marcel,

which quantity exactly would you like to compute?

Best Regards

Patrick

It is not exactly a quantity that I am looking for, but rather a quality or a pattern. I am wondering if members of a given r-dimensional subspace  come in clusters (sub-sequences with successive gaps smaller than the order s of the recursion) or if they come evenly or randomly spread over an entire period.

There are two somewhat conflicting views:

(1) given that qr is much smaller than qs ,the probability of finding a dependent vector in the vicinity of a given position  is next to zero.

(2) On the other hand, if you are at a vector (v, say) of  the subspace, and you take the block of s successive powers starting at that vector v, this must be a basis of the entire linear space. Then it can be seen that at least s-r elements of the block are not in the linear subspace. That still leaves you with r-1  potential members of the subspace in a relatively short range following v.

I made a few tests with Maple involving binary primitive polynomials of degree s=8, 10, 13  and one ternary primitive polynomial of degree s=8. (Good polynomials have weight close to s/2.) In the binary case I found one cluster with two nearby (= distance

I think your dependencies between powers of alpha are essentially codewords in the dual code, ie a hamming cyclic code in the binary case. The weight distribution is known of course. Maybe you need some more refined measure than the Hamming weight like the support distribution of subcodes of given rank something like that to model your idea of "scattering".

Patrick,

Nice suggestion. I had not yet taken the coding view: my problem indeed links up with Hamming distance, although --strictly speaking-- it is about difference in the exponent of the generator. I'll think about this. In the mean time I proved the following (with s as the recursion order): the probability of having a linearly dependent subset of a given size r < s is next to zero unless r is very nearly s: I took the sizes s = 521, 607, 1279 (exponents of a Mersenne prime), q = a prime power, and r = 99.5 percent of s; p(s) is the exact (up-rounded) probability for an r-set to be independent.

 q         p(521)           p(607)        p(1279)

-----------------------------------------------------

 4  .9792533861 .9947970907 .9999186211

 8  .9977684107 .9997209908 .9999994550

16 .9997395873 .9999837240 .9999999960

32 .9999684980 .9999990156 1.000000000

------------------------------------------------------

The result does not depend on the primitive polynomial that is being used.

Actually if q=2 and r>=3 and n=2^s-1 then this probability is directly linked to the weight distribution A_i of the dual. Thus p(r)=(A_r/2^k), where k is the dimension of Hamming code: k=n-s.

I've been doing some reading lately. The probability I referred to is actually somewhat simpler than the weight distribution mentioned by Patrick: the probability ps(r) to have an independent sequence of length r < s in an m-sequence of dimension s is given by the fairly straightforward formula

product for {i=0} to {r-1} ( qs - qi ) / ( r! * binomial(qs-1, r) ,

where q is the size of the field. The formula for the number Ar of words of length r with a dependency can be derived from this and is somewhat more complex. I found some other valuable information in a few papers on low-weight polynomials that are divisible by a given primitive polynomial; e.g., Maitra et al (reference below). This paper, like most others, concentrates on binary sequences (q = 2). When Maitra et al talk about "low degree" (which is what I am looking for), they actually mean degree < 2s - 1. For large s (many hundreds, or even several thousands) this is no longer realistic.

I found an old reference which gives Ar for general finite fields (reference Laksov). I saw that Thm. 1 of Maitra et al can be generalized to any finite field Fq and produces a t-nomial of degree n*s divided by a primitive polynomial of degree s if n is relatively prime with qs -1.

Article Results on multiples of primitive polynomials and their prod...

Article Linear Recurring Sequences over Finite Fields.