[math-fun] Re: Path Question
I wrote:
Good question! What I think I mean is that if we let k denote the length of s and define f(N) as the number of occurrences of s in the first N bits of S, then the discrepancy d(N) = f(N) - (N-k+1)/2^k satisfies |d(N)| < C (log N) / N for some constant C, when N is sufficiently large.
Oops: make that "|d(N)| < C (log N)"! (Note that the difference between (N-k+1)/2^k and N/2^k is constant and hence less than log N for N sufficiently large; so another way to state the desired inequality is |f(N)/N - 1/2^k| < C (log N) / N.) I hope I have that right now... Fred Lunnon wrote:
Perhaps it's worth mentioning a bomb-proof but clumsier alternative. deBruijn sequences --- (k!)^k^(n-1)/k^n disitnct ones, modulo cyclic shift --- exist for every span n and base k (with k = 2 here). So at each iteration pick any one with span n' = 2^n, then shift it until the previous one with span n appears at the front.
Can you explain in more detail how this works? I'm not seeing it. Jim
On 4/18/07, James Propp <propp@math.wisc.edu> wrote:
Fred Lunnon wrote:
Perhaps it's worth mentioning a bomb-proof but clumsier alternative. deBruijn sequences --- (k!)^k^(n-1)/k^n distinct ones, modulo cyclic shift --- exist for every span n and base k (with k = 2 here). So at each iteration pick any one with span n' = 2^n, then shift it until the previous one with span n appears at the front.
Can you explain in more detail how this works? I'm not seeing it.
Jim
Starting with n = 1: S = 01; there's no choice about the next iteration n = 2: S = 0110; now generate any old deBruijn sequence with span 4 --- say the first in numerical order, 000010 0110 101111 --- and shift it until the previous S (occurring as a factor at just one position, by definition of deBruijn sequence) lies at the front n = 4: S = 0110101111000010; at the next iteration we shall generate 65536 bits, which I fear our moderator might consider immoderate ... For the Galois sequence variation, the algorithm must generate primitive polynomials (to generate each new finite sequence) and compute discrete logarithms (to locate the old as a factor of the new). Fred Lunnon
On 4/18/07, Fred lunnon <fred.lunnon@gmail.com> wrote:
For the Galois sequence variation, the algorithm must generate primitive polynomials (to generate each new finite sequence) and compute discrete logarithms (to locate the old as a factor of the new).
No, you don't need discrete logs at all --- simply start the new FSR sequence from the (full period of) the old one. And similarly, the new deBruijn sequence can be generated starting from the old, with no need to shift it cyclically. WFL
The trouble with this (exponentially increasing) de Bruijn construction is that --- as might be expected --- it's insufficiently constrained, which becomes immediately apparent on inspecting the length 65536 segment. For instance, using the numerically earliest possible span-16 deBruijn sequence, the sum of the first 1024 digits is only 228. For fixed word size, such imbalances will only worsen as as the construction proceeds. Galois sequences have to be a better prospect from this point of view. WFL
participants (2)
-
Fred lunnon -
James Propp