Torsten Sillke, FRA, 1998-08 How many words have the same autocorrelation value? At the beginning of the 80th Achim Flammenkamp and I were interested in Conway's formular of the flipping coin game described in [Gardner 74]. Proof of the recurences given here can be found in [L. J. Guibas, A. M. Odlyzko, 1981, Periods in Strings, Thm 7.1]. Given the autocorrelation-function it is natural to ask for their inverse (over a given alphabet). Let's count X2[a] = # autocorrelation2^(-1) = # { w in 0{0, 1}^* | w:w = a } X3[a] = # autocorrelation3^(-1) = # { w in 0{0, 1, 2}^* | w:w = a } Xq[a] = # autocorrelation_q^(-1) = # { w in 0{0, 1, ..., q-1}^* | w:w = a } (The notion u:v is called the correlation function. It is explained at the end of this text.) Then we determined the sequences X2[ 2^n + const ]. At the end this leads to a recursion for X2[a]. Let A2[n] be the the number of words of length n over the alphabet {0, 1} beginning with '0' and trivial (2^(n-1)) autocorrelation-function. A2[n] = X2[2^(n-1)]. The A2[n] satisfies the following recursion formular A2[1] = 1 A2[2n] = 2 A2[2n-1] - A2[n] for n >= 1 A2[2n+1] = 2 A2[2n] for n >= 1 Let B2[n] be the the number of words of length n over the alphabet {0, 1} beginning with '0' and the autocorrelation-function is 2^(n-1)+1. B2[n] = X2[2^(n-1)+1]. The B2[n] satisfies the following recursion formular B2[2] = 1 B2[2n-1] = 2 B2[2n-2] - B2[n] for n >= 2 B2[2n] = 2 B2[2n-1] + B2[n] for n >= 2 Let C2[n] be the the number of binary words beginning with '0' of length n with autocorrelation-function is 2^(n-1) + 2 C2[3] = 0, C2[4] = 1, C2[2n-1] = 2 C2[2n-2] + 2 C2[n] for n >= 3 C2[2n] = 2 C2[2n-1] - C2[n] - C2[n+1] for n >= 3 Let D2[n] be the the number of binary words beginning with '0' of length n with autocorrelation-function is 2^(n-1) + 3 D2[3] = 1, D2[4] = 0, D2[2n-1] = 2 D2[2n-2] + D2[n] for n >= 3 D2[2n] = 2 D2[2n-1] + D2[n] - D2[n+1] for n >= 3 Table with A2[1..19] to D2[1..19]: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ------------------------------------------------------------------------- A2 | 1 1 2 3 6 10 20 37 74 142 284 558 1116 2212 4424 8811 17622 35170 70340 B2 | 0 1 1 3 5 11 19 41 77 159 307 625 1231 2481 4921 9883 19689 39455 78751 C2 | 0 0 0 1 2 3 8 13 30 55 116 221 458 895 1816 3589 7238 14391 28892 D2 | 0 0 1 0 1 3 6 11 23 44 91 179 364 723 1457 2902 5827 11633 23310 The general recursion for autocorrelation-function 2^(n-1) + c has been figured out from the sequences by Achim as E2[2n-1,c] = 2 E2[2n-2,c] + Sum_{k>=0} alpha2(c,2k) E2[n+k,c] E2[2n,c] = 2 E2[2n-1,c] + Sum_{k>=0} alpha2(c,2k-1) E2[n+k,c] with n >= log2(c)+2. were the function alpha2 is alpha2(c, k) = phi( floor(c / 2^k) ) for k >= 0 alpha2(c,-1) = (-1)^(c+1) with 4-periodic function phi which is phi(n) = 0 for n = 0 mod 4 phi(n) = -1 for n = 1 mod 4 phi(n) = 2 for n = 2 mod 4 phi(n) = 1 for n = 3 mod 4 Let bit(c, k) be the k-th digit of the binarey representation of c then alpha2(c, k) = 2 bit(c, k+1) - bit(c, k) for k >= 0 alpha2(c, k) = 2 bit(2c+1, k+2) - bit(2c+1, k+1) for k >= -1 For CS-guys this is the negative of a 2-bit complement on two bits. I found this on old scratch notes of Achim. Now have a found a recursion for X2(2^(n-1)+c) if n is big enought. For the small n we found the relation X2[ 2^(n-1) + c ] = X2[c] * [ X2[ 2^(n-1) + c ] > 0 ]. The condition X2[ 2^(n-1) + c ] > 0 is the existance problem and conditions can be found in [L. J. Guibas, A. M. Odlyzko 1981]. This test is linear in n. >> Does anyone want to prove this. Upto now its only numerical evidence. << The asymtotic distribution: a2 = lim_{n->oo} 2 A2[n] / 2^n b2 = lim_{n->oo} 2 B2[n] / 2^n c2 = lim_{n->oo} 2 C2[n] / 2^n d2 = lim_{n->oo} 2 D2[n] / 2^n The constants computed upto 220 digits. a2 = 0.2677868402178891123766714035843025525550598979934845320763118885112149\ 3778523276285354476223856136843466446447207331150068764671638142714485\ 4162563424029263893834402719055447409920457941095037971765840156929107\ 6474696957 b2 = 0.3004200715183032992623000629138269940101525070873926867827513580421691\ 0146436463481739497550314671803707924354053091385644383653256162168099\ 3261751049121521315106374913548420203105266729981760100988282367635056\ 0682228172 c2 = 0.1100006178936985734131570526893565999590139052432740489362517829054628\ 7042274434273696252032772369441572276551963931644825633440026404816509\ 0948221935970749579220900186497336352972745452741530739949068426643198\ 0246026503 (rounded up) d2 = 0.0889181298966659907350220843279202341357222705719268070312236381660997\ 0236256949222332049616300280832126610497725638778865262552776695991294\ 1152276475767170778796370188263291643369812442854056340704551680525377\ 0720538761 (rounded up) Let A3[n] be the the number of trinary words beginning with '0' of length n with autocorrelation-function is 2^(n-1) A3[1] = 1 A3[2n] = 3 A3[2n-1] - A3[n] for n >= 1 A3[2n+1] = 3 A3[2n] for n >= 1 Let B3[n] be the the number of trinary words beginning with '0' of length n with autocorrelation-function is 2^(n-1) + 1 B3[2] = 1 B3[2n-1] = 3 B3[2n-2] - B3[n] for n >= 2 B3[2n] = 3 B3[2n-1] + 2 B3[n] for n >= 2 Let C3[n] be the the number of trinary words beginning with '0' of length n with autocorrelation-function is 2^(n-1) + 2 C3[3] = 0, C3[4] = 1, C3[2n-1] = 3 C3[2n-2] + 3 C3[n] for n >= 3 C3[2n] = 3 C3[2n-1] - C3[n] - C3[n+1] for n >= 3 Let D3[n] be the the number of trinary words beginning with '0' of length n with autocorrelation-function is 2^(n-1) + 3 D3[3] = 1, D3[4] = 0, D3[2n-1] = 3 D3[2n-2] + 2 D3[n] for n >= 3 D3[2n] = 3 D3[2n-1] + 2 D3[n] - D3[n+1] for n >= 3 The general recursion for autocorrelation-function 2^(n-1) + c for trinary is only a minor modification of the binary case E3[2n-1,c] = 3 E3[2n-2,c] + Sum_{k>=0} alpha3(c,2k) E3[n+k,c] E3[2n,c] = 3 E3[2n-1,c] + Sum_{k>=0} alpha3(c,2k-1) E3[n+k,c] with n >= log2(c)+2. were the function alpha3 is alpha3(c, k) = 3 bit(c, k+1) - bit(c, k) for k >= 0 alpha3(c, k) = 3 bit(2c+1, k+2) - bit(2c+1, k+1) for k >= -1 Table for A3[1..15] to D3[1..15]: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ----------------------------------------------------------------------- A3 | 1 2 6 16 48 138 414 1226 3678 10986 32958 98736 296208 888210 2664630 B3 | 0 1 2 8 22 70 202 622 1844 5576 16658 50114 150140 450824 1351850 C3 | 0 0 0 2 6 16 54 154 480 1418 4302 12836 38670 115802 347868 D3 | 0 0 1 0 2 8 24 70 214 638 1930 5782 17394 52160 156620 The asymtotic distribution: a3 = lim_{n->oo} 3 A3[n] / 3^n b3 = lim_{n->oo} 3 B3[n] / 3^n c3 = lim_{n->oo} 3 C3[n] / 3^n d3 = lim_{n->oo} 3 D3[n] / 3^n a3 = 0.5569798397642302936529413190253562568356116596037690340763309094999085\ 1780730306956028402504861427967790182789312028427637802168971096220362\ 1489594129456583997631343841686628944611138438126200325850816360025697\ 3466732885 b3 = 0.2827034817373881146782811193909497299945354251057943466765630402481567\ 6228069173288200768054246000793888267504084114755913761559836490021509\ 9858622653129392437975497843792146697661788691686656526157148139715463\ 9805627295 c3 = 0.0727142716159324649840419361244568137627400696736768207103315826950236\ 9815108290996358418512269367089360144975390806834534257712409313844687\ 3360898085140800690035612827942364702385847119494994385100600332132872\ 8914302905 d4 = 0.0327526253473105285996333406811766068576604014578791099470569986630700\ 6693583957279220877939108696928256871442518761892569096544602813922122\ 8713506308644144490026127116930469708806876182491611005606617372088677\ 7025953082 Who can improve the asymtotic formulars? Evaluating the recurrences gives an linear algorithm for determing these constants. Can this be improved? I don't think that this are known constants. The correlation function: (notation from 'Concete Mathematics') Let W be a word of length L(W) the denote W^(k) and W_(k) respectively the last k charactern and the first k charecters of W. Then the correlation function between two word U and V is U:V = Sum_{1<=k<=min(L(U),L(V))} 2^(k-1) [ U^(k) = B_(k) ] The autocorrelation of a word W is then W:W Example (from 'Concete Mathematics') A = HTHTHHTHTH A:A = (1000010101)_2 = 512 + 16 + 4 + 1 = 533 HTHTHHTHTH ok HTHTHHTHTH HTHTHHTHTH HTHTHHTHTH HTHTHHTHTH HTHTHHTHTH ok HTHTHHTHTH HTHTHHTHTH ok HTHTHHTHTH HTHTHHTHTH ok References: - EIS A2 = A045690, 2*A2 = A003000; - A. Benczur, I. Katai; On the number of occurences of sequences patterns, Acta Math. Hungarica, 47 (1986) 371-382 Zbl 625.68053 (not reviewed) - Gunnar Blom; Problem 94-20: Overlapping binary sequences, SIAM Review 37 (1995), 619-620 - Martin 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 - 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 - D. J. Greaves, Stephen J. Montgomery-Smith; Unforgeable Marker Sequences, http://www.math.missouri.edu/~stephen/preprints/unforgeable/ An application of the series A2. They determine a2 as a series. - Leo J. Guibas, Andrew M. Odlyzko; Periods in Strings, Journal of Combinatorial Theory A 30 (1981) 19-42 Zbl 464.68070 Section 7: Populations Their L_n(C,q) is another form of my q * Xq[2^(n-1) + C]. Thm 7.1 gives the basic recurrence for this population. (the beta value table one p37 list the constants a2, b2, c2, d2, a3, b3, c3, d3, a24, b24) - Leo J. Guibas, Andrew M. Odlyzko; String Overlaps, Patterns, Matching and Nontransitive Games, Journal of Combinatorial Theory A 30 (1981) 183-208 Zbl 454.68109 - Heiko Harborth; Endliche 0-1-Folgen mit gleichen Teilbl\"ocken, Journal f\"ur Reine und Angewandte Mathematik, 271 (1974) 139-154, Zbl 297.05008 (als Habilitationsschrift der nat. Fakult\"at der TU Braunschweig angenommen) his L(0,k) is 2*A2[k]. - P. Tolstrup Nielsen; A note on bifix-free sequences, IEEE Trans. Info. Theory IT-19 (1973), 704-706 Table of initial values for binary sequences: Entries marked '-' are not defined and the marked '.' ones are zero. The nonzero entries in line c are X2(c). (The c which give zero sequences have been ommitted.) c | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 --------+------------------------------------------------ 0 | 1 1 | - 1 10 | - - . 1 11 | - - 1 . 100 | - - - . . 2 101 | - - - . 1 1 111 | - - - 1 . . 1000 | - - - - . . . 3 1001 | - - - - . . 3 3 1010 | - - - - . 1 . . 1111 | - - - - 1 . . . 10000 | - - - - - . . . . 6 10001 | - - - - - . . . 5 5 10010 | - - - - - . . 2 . 2 10011 | - - - - - . . 1 1 1 10101 | - - - - - . 1 . . 1 11111 | - - - - - 1 . . . . 100000 | - - - - - - . . . . . 10 100001 | - - - - - - . . . . 11 11 100010 | - - - - - - . . . 3 . 3 100011 | - - - - - - . . . 3 3 3 100100 | - - - - - - . . 2 . . . 100101 | - - - - - - . . 1 . 1 . 101010 | - - - - - - . 1 . . . . 111111 | - - - - - - 1 . . . . . 1000000 | - - - - - - - . . . . . . 20 1000001 | - - - - - - - . . . . . 19 19 1000010 | - - - - - - - . . . . 8 . 8 1000011 | - - - - - - - . . . . 6 6 6 1000100 | - - - - - - - . . . 4 . . 4 1000101 | - - - - - - - . . . 1 . 1 1 1000111 | - - - - - - - . . . 1 1 1 1 1001001 | - - - - - - - . . 3 . . . 3 1010101 | - - - - - - - . 1 . . . . 1 1111111 | - - - - - - - 1 . . . . . . 10000000 | - - - - - - - - . . . . . . . 37 10000001 | - - - - - - - - . . . . . . 41 41 10000010 | - - - - - - - - . . . . . 13 . 13 10000011 | - - - - - - - - . . . . . 11 11 11 10000100 | - - - - - - - - . . . . 8 . . 8 10000101 | - - - - - - - - . . . . 4 . 4 4 10000111 | - - - - - - - - . . . . 3 3 3 3 10001000 | - - - - - - - - . . . 3 . . . . 10001001 | - - - - - - - - . . . 3 . . 3 . 10010010 | - - - - - - - - . . 2 . . . . 2 10010011 | - - - - - - - - . . 1 . . . 1 1 10101010 | - - - - - - - - . 1 . . . . . . 11111111 | - - - - - - - - 1 . . . . . . . -- mailto:Torsten.Sillke@uni-bielefeld.de http://www.mathematik.uni-bielefeld.de/~sillke/