The autocorrelation function auto() is a mapping from
{0,1}^n to {0,1}^N for each n greater than zero.
(Let N be the set of positive integers.)

An old question is:

  What is the size of the range of auto().
  Let the size be s(n) = # auto({0,1}^n).


The Autocorrelation is defined as

  auto(s) = correlation(s,s)

where the Correlation-function is defined as

  correlation(s1, s2) = 

    indicator(length({ w in {0,1}^* | s1 = x.w, s2 = w.y, #w > 0 }))


Example:

   s1 = 10101, s2 = 10110,

   CS = { w in {0,1}^* | s1 = x.w, s2 = w.y, #w > 0 } = { 1, 101 }

   CL = length(CS) = length({ 1, 101 }) = { 1, 3 }

   C  = indicator(CL) = indicator({ 1, 3 })

      = f : N -> {0,1} with f(n) = 1 if n element { 1, 3 } else 0.


Theorem: (Guibas, Odlyzko 1981)

  1/(2*ln(2)) * ln(n)^2 + O(ln(n)) <= ln(s(n)) <= 1/(2*ln(1.5)) * ln(n)^2 + O(ln(n))


Conjecture: (Flammenkamp, Sillke 1984)

  ln(s(n)) = 1/(2*ln(2)) * ln(n)^2 + o(ln(n)^2)

Table:
  n  1 2 3 4 5 6  7  8  9 10 11 12 13 14 15 16 17 18  19  20  21  22  23  24  25
s(n) 1 2 3 4 6 8 10 13 17 21 27 30 37 47 57 62 75 87 102 116 135 155 180 194 220


EIS entry: %N A005434 Correlations of length n.


References:

- A. Benczur, I. Katai;
  On the number of occurences of sequences patterns,
  Acta Math. Hungarica, 47 (1986) 371-382

- Benveneto;
  The occurrence of sequence pattern in ergodic Markov chains,
  Stochastic Processes and their Applications, 17 (1984) 369-373

- Blom, Thorburn;
  How many random digits are required until given sequences are obtained,
  Journal of Applied Probability 19 (1982) 518-531.

- A. Flammenkamp, T. Sillke;
  Table of s() upto 800 and further refinements of s().

- M. Gardner;
  On the Paradoxial Situations that Arise from Nontransitive Relations,
  Scientific American, 231:4 (October 1974) 120-124.
  Preprinted in his: Time Travel and Other Mathematical Bewilderments
  Freeman (1988) New York, Chap 5: Nontransitive Paradoxes, 55-69

- H. U. Gerber, S. Y. R. Li;
  The Occurence of Sequence Patterns,
  Stochastic Processes and their Applications, 11 (1981) 101-108

- Ronald L. Graham, Donald E. Knuth, Oren Patashnik;
  Concrete mathematics: a foundation for computer science,
  Addison-Wesley Publ., Amsterdam, 2nd Ed., 1994.
  Zbl 668.00003 (1st Ed.)
  Zbl 836.00001 (2nd Ed.)
  Section 8.4: Flipping Coins

- L. J. Guibas;
  Periodicities in Strings,
  Combinatorial Algorithms on Words 1985, NATO ASI Vol. F12, 257-269

- L. J. Guibas, A. M. Odlyzko;
  Periods in Strings,
  Journal of Combinatorial Theory A 30:1 (1981) 19-42

- L. J. Guibas, A. M. Odlyzko;
  String Overlaps, Patterns, Matching and Nontransitive Games,
  Journal of Combinatorial Theory A 30 (1981) 183-208

- H. Harborth;
  Endliche 0-1-Folgen mit gleichen Teilbloecken,
  Journal fuer Mathematik, 271 (1974) 139-154,
  (als Habilitationsschrift der nat. Fakultaet der TU Braunschweig angenommen)

- D. M. Jackson, I. P. Goulden;
  Algebraic Methods for Permutations with Prescribed Patterns,
  Advances in Mathematics, 42:2 (Nov. 1981) 113-135

- N. L. Johnson, S. Kotz;
  Urn Models and Their Applications,
  Wiley, New York, 1977
  (p64 - 68)

- Shuo Yen R. Li;
  A Maringale Approach to the Study of Occurence,
  The Annals of Probability, 8 (1980) 1171-1176

- A. D. Solov'ev;
  A combinatorial identity and its application to the problem
  concerning the first occurence of a rare event,
  Theory of Probability and its Applications, 11 (1966) 276-282

- V. R. R. Uppuluri, S. A. Patli;
  Waiting Times and Generalized Fibonacci Sequences,
  The Fibonacci Quaterly, (Nov. 1983) 242-249

--
mailto:Torsten.Sillke@uni-bielefeld.de
http://www.mathematik.uni-bielefeld.de/~sillke/