On the correlation of binary sequences

In a series of papers Mauduit and Sárközy (partly with further coauthors) studied finite pseudorandom binary sequences. In particular, one of the most important applications of pseudorandomness is cryptography. If, e.g., we want to use a binary sequence E_N{-1,+1}^N (after transforming it into a bit sequence) as a key stream in the standard Vernam cipher [A. Menezes, P. van Oorschot, R. Vanstone, Handbook of Applied Cryptography, CRC Press, Boca Raton, 1997], then E_N must possess certain pseudorandom properties. Does E_N need to possess both small well-distribution measure and, for any fixed small k, small correlation measure of order k? In other words, if W(E_N) is large, resp. C_k(E_N) is large for some fixed small k, then can the enemy utilize this fact to break the code? The most natural line of attack is the exhaustive search: the attacker may try all the binary sequences E_N{-1,+1}^N with large W(E_N), resp. large C_k(E_N), as a potential key stream. Clearly, this attack is really threatening only if the number of sequences E_N{-1,+1}^N with

(i) large W(E_N), resp.

(ii) large C_k(E_N)

is “much less” than the total number 2^N of sequences in {-1,+1}^N, besides one needs a fast algorithm to generate the sequences of type (i), resp. (ii).The case (i) is easy, thus, for the sake of completeness, here we just present an estimate for the number of sequences E_N with large W(E_N).The case (ii), i.e., the case of large correlation is much more interesting: this case will be studied in Section 2.In Section 3 we will sharpen the results of Section 2 in the special case when the order of the correlation is 2.Finally, in Section 4 we will study a lemma, which plays a crucial role in the estimation of the correlation in some of the most important constructions of pseudorandom binary sequences.     

Optimal conflict-avoiding codes of length <Emphasis Type="Italic">n</Emphasis> ≡ 0 (mod 16) and weight 3

A conflict-avoiding code of length n and weight k is defined as a set of binary vectors, called codewords, all of Hamming weight k such that the distance of arbitrary cyclic shifts of two distinct codewords in C is at least 2k−2. In this paper, we obtain direct constructions for optimal conflict-avoiding codes of length n = 16m and weight 3 for any m by utilizing Skolem type sequences. We also show that for the case n = 16m + 8 Skolem type sequences can give more concise constructions than the ones obtained earlier by Jimbo et al.      

Periodicity and Correlation Properties of d-FCSR Sequences

A d-feedback-with-carry shift register (d-FCSR) is a finite state machine, similar to a linear feedback shift register (LFSR), in which a small amount of memory and a delay (by d-clock cycles) is used in the feedback algorithm (see Goresky and Klapper [4,5]). The output sequences of these simple devices may be described using arithmetic in a ramified extension field of the rational numbers. In this paper we show how many of these sequences may also be described using simple integer arithmetic, and consequently how to find such sequences with large periods. We also analyze the arithmetic cross-correlation between pairs of these sequences and show that it often vanishes identically.     

Random suffix search trees

A random suffix search tree is a binary search tree constructed for the suffixes X_i = 0 · B_iB_i+1B_i+2… of a sequence B₁, B₂, B₃, … of independent identically distributed random b‐ary digits B_j. Let D_n denote the depth of the node for X_n in this tree when B₁ is uniform on ?_b. We show that for any value of b > 1, ??D_n = 2 log n + O(log²log n), just as for the random binary search tree. We also show that D_n/??D_n → 1 in probability. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2003     

RECONSTRUCTION OF BINARY RELATIONS FROM THEIR RESTRICTIONS OF CARDINALITY 2, 3, 4 and (n - 1) II

We shall prove here that any binary relation on a base E with cardinality n > 6 is reconstructible from its restrictions of cardinality 2, 3, 4 and (n - 1). This proof needs results of part I of this paper where we characterize any pair of relations R, R' which are 2-, 3- and 4-hypomorphic. As a corollary we obtain that any binary relation is (n - 4)-reconstructible (when n > 9).     

Learning finite binary sequences from half‐space data

The problem of inferring a finite binary sequence w *∈{−1, 1}ⁿ is considered. It is supposed that at epochs t=1, 2,…, the learner is provided with random half‐space data in the form of finite binary sequences u ^(t)∈{−1, 1}ⁿ which have positive inner‐product with w *. The goal of the learner is to determine the underlying sequence w * in an efficient, on‐line fashion from the data { u ^(t), t≥1}. In this context, it is shown that the randomized, on‐line directed drift algorithm produces a sequence of hypotheses {w^(t)∈{−1, 1}ⁿ, t≥1} which converges to w * in finite time with probability 1. It is shown that while the algorithm has a minimal space complexity of 2n bits of scratch memory, it has exponential time complexity with an expected mistake bound of order Ω(e^0.139n). Batch incarnations of the algorithm are introduced which allow for massive improvements in running time with a relatively small cost in space (batch size). In particular, using a batch of 𝒪(n log n) examples at each update epoch reduces the expected mistake bound of the (batch) algorithm to 𝒪(n) (in an asynchronous bit update mode) and 𝒪(1) (in a synchronous bit update mode). The problem considered here is related to binary integer programming and to learning in a mathematical model of a neuron. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14, 345–381 (1999)     

A study of random Weyl trees

We study binary search trees constructed from Weyl sequences {nθ}, n≥1, where θ is an irrational and {·} denotes “mod 1.” We explore various properties of the structure of these trees, and relate them to the continued fraction expansion of θ. If H_n is the height of the tree with n nodes when θ is chosen at random and uniformly on [0, 1], then we show that in probability, H_n∼(12/π²)log n log log n. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12, 271–295, 1998     

How Many Bits have to be Changed to Decrease the Linear Complexity?

The k-error linear complexity of periodic binary sequences is defined to be the smallest linear complexity that can be obtained by changing k or fewer bits of the sequence per period. For the period length p ⁿ, where p is an odd prime and 2 is a primitive root modulo p ², we show a relationship between the linear complexity and the minimum value k for which the k-error linear complexity is strictly less than the linear complexity. Moreover, we describe an algorithm to determine the k-error linear complexity of a given p ⁿ-periodic binary sequence.     

On evaluating the linear complexity of a sequence of least period 2 n

The linear complexity of a periodic binary sequence is the length of the shortest linear feedback shift register that can be used to generate that sequence. When the sequence has least period 2 ⁿ ,n0, there is a fast algorithm due to Games and Chan that evaluates this linear complexity. In this paper a related algorithm is presented that obtains the linear complexity of the sequence requiring, on average for sequences of period 2 ⁿ ,n0, no more than 2 parity checks sums.     

The structure of graphs with given lengths of cycles

The cycle spectrum of a given graph G is the lengths of cycles in G. In this paper, we introduce the following problem: determining the maximum number of edges of an n-vertex graph with given cycle spectrum. In particular, we determine the maximum number of edges of an n-vertex graph without containing cycles of lengths three and at least k. This can be viewed as an extension of a well-known result of Erd?s and Gallai concerning the maximum number of edges of an n-vertex graph without containing cycles of lengths at least k. We also determine the maximum number of edges of an n-vertex graph whose cycle spectrum is a subset of two positive integers.     

Left and Right Length of Paths in Binary Trees or on a Question of Knuth

We consider extended binary trees and study the joint right and left depth of leaf j, where the leaves are labelled from left to right by 0, 1, . . . , n, and the joint right and left external pathlength of binary trees of size n. Under the random tree model, i.e., the Catalan model, we characterize the joint limiting distribution of the suitably scaled left depth and the difference between the right and the left depth of leaf j in a random size-n binary tree when j ~ ρn with 0 < ρ > 1, as well as the joint limiting distribution of the suitably scaled left external pathlength and the difference between the right and the left external pathlength of a random size-n binary tree. This work was supported by the Austrian Science Foundation FWF, grant S9608-N13.     

Hadamard matrices of small order and Yang conjecture

We show that 138 odd values of n<10000 for which a Hadamard matrix of order 4n exists have been overlooked in the recent handbook of combinatorial designs. There are four additional odd n=191, 5767, 7081, 8249 in that range for which Hadamard matrices of order 4n exist. There is a unique equivalence class of near‐normal sequences NN(36), and the same is true for NN(38) and NN(40). This means that the Yang conjecture on the existence of near‐normal sequences NN(n) has been verified for all even n⩽40, but it still remains open. © 2010 Wiley Periodicals, Inc. J Combin Designs 18: 254–259, 2010     

Remarks on the <Emphasis Type="Italic">k</Emphasis>-error linear complexity of <Emphasis Type="Italic">p</Emphasis><Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>-periodic sequences

Recently the first author presented exact formulas for the number of 2 ⁿ -periodic binary sequences with given 1-error linear complexity, and an exact formula for the expected 1-error linear complexity and upper and lower bounds for the expected k-error linear complexity, k ≥ 2, of a random 2 ⁿ -periodic binary sequence. A crucial role for the analysis played the Chan–Games algorithm. We use a more sophisticated generalization of the Chan–Games algorithm by Ding et al. to obtain exact formulas for the counting function and the expected value for the 1-error linear complexity for p ⁿ -periodic sequences over prime. Additionally we discuss the calculation of lower and upper bounds on the k-error linear complexity of p ⁿ -periodic sequences over .      

Characterization of 2<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>-periodic binary sequences with fixed 2-error or 3-error linear complexity

The linear complexity of sequences is an important measure of the cryptographic strength of key streams used in stream ciphers. The instability of linear complexity caused by changing a few symbols of sequences can be measured using k-error linear complexity. In their SETA 2006 paper, Fu et al. (SETA, pp. 88–103, 2006) studied the linear complexity and the 1-error linear complexity of 2 ⁿ -periodic binary sequences to characterize such sequences with fixed 1-error linear complexity. In this paper we study the linear complexity and the k-error linear complexity of 2 ⁿ -periodic binary sequences in a more general setting using a combination of algebraic, combinatorial, and algorithmic methods. This approach allows us to characterize 2 ⁿ -periodic binary sequences with fixed 2- or 3-error linear complexity. Using this characterization we obtain the counting function for the number of 2 ⁿ -periodic binary sequences with fixed k-error linear complexity for k = 2 and 3.     

On the Unitary Binary Group

One consider the variety of the unitary binary group in n variables and it is shown that this algebraic variety is rational and it has n² parameters. Then it is given a parametrical rational representation of this variety.AMS Subject Classification (1991) 20G20     

Constructions of Small Complete Caps in Binary Projective Spaces

In the binary projective spaces PG(n,2) k-caps are called large if k > 2^n-1 and smallif k ≤ 2^n-1. In this paper we propose new constructions producing infinite families of small binary complete caps.AMS Classification: 51E21, 51E22, 94B05     

Upper and Lower Bounds on Maximum Nonlinearity of n-input m-output Boolean Function

The paper presents lower and upper bounds on the maximumnonlinearity for an n-input m-output Booleanfunction. We show a systematic construction method for a highlynonlinear Boolean function based on binary linear codes whichcontain the first order Reed-Muller code as a subcode. We alsopresent a method to prove the nonexistence of some nonlinearBoolean functions by using nonexistence results on binary linearcodes. Such construction and nonexistence results can be regardedas lower and upper bounds on the maximum nonlinearity. For somen and m, these bounds are tighter than theconventional bounds. The techniques employed here indicate astrong connection between binary linear codes and nonlinear n-input m-output Boolean functions.     

The Hamming weight of the non-adjacent-form under various input statistics

The Hamming weight of the non-adjacent form is studied in relation to the Hamming weight of the standard binary expansion. In particular, we investigate the expected Hamming weight of the NAF of an n-digit binary expansion with k ones where k is either fixed or proportional to n. The expected Hamming weight of NAFs of binary expansions with large (≥ n/2) Hamming weight is studied. Finally, the covariance of the Hamming weights of the binary expansion and the NAF is computed. Asymptotically, these Hamming weights become independent and normally distributed. Communicated by Attila Pethő     

Distribution of the Number of Successes in Success Runs of Length at Least <Emphasis Type="Italic">k</Emphasis> in Higher-Order Markovian Sequences

We consider the distribution of the number of successes in success runs of length at least k in a binary sequence. One important application of this statistic is in the detection of tandem repeats among DNA sequence segments. In the literature, its distribution has been computed for independent sequences and Markovian sequences of order one. We extend these results to Markovian sequences of a general order. We also show that the statistic can be represented as a function of the number of overlapping success runs of lengths k and k + 1 in the sequence, and give immediate consequences of this representation. AMS 2000 Subject Classification 60E05, 60J05     

Minors of a random binary matroid

Let A be an n × m matrix over GF ₂ where each column consists of k ones, and let M be an arbitrary fixed binary matroid. The matroid growth rate theorem implies that there is a constant C_M such that m ≥ C_Mn² implies that the binary matroid induced by A contains M as a minor. We prove that if the columns of A = A _n,m,k are chosen randomly, then there are constants k_M,L_M such that k ≥ k_M and m ≥ L_Mn implies that A contains M as a minor with high probability .