On Decimations of l-Sequences

SIAM Journal on Discrete Math, 18 (2004) 130-140.

Andrew Klapper, 779A Anderson Hall, Dept. of Computer Science, University of Kentucky, Lexington, KY, 40506-0046, klapper at cs.uky.edu. www.cs.uky.edu/~klapper/andy.html
Mark Goresky, Institute for Advanced Study
Ram Murthy, Queen's University
Igor Shparlinski, Macquarie University

Abstract Maximal length Feedback with Carry Shift Register sequences have several remarkable statistical properties. Among them is the property that the arithmetic correlations between any two cyclically distinct decimations are precisely zero. It is open, however, whether all such pairs of decimations are indeed cyclically distinct. In this paper we show that the set of distinct decimations is large and, in some cases, all decimations are distinct.

Index Terms -- feedback with carry shift register, arithmetic correlation, exponential sum, binary sequence, p-adic number.