Periodic multisequences with large error linear complexity

Generalizing the theory of k-error linear complexity for single sequences over a finite field, Meidl et al. (J. Complexity 23(2), 169–192 (2007)) introduced three possibilities of defining error linear complexity measures for multisequences. A good keystream sequence must possess a large linear complexity and a large k-error linear complexity simultaneously for suitable values of k. In this direction several results on the existence, and lower bounds on the number, of single sequences with large k-error linear complexity were proved in Meidl and Niederreiter (Appl. Algebra Eng. Commun. Comput. 14(4), 273–286 (2003)), Niederreiter (IEEE Trans. Inform. Theory 49(2), 501–505 (2003)) and Niederreiter and Shparlinski (In: Paterson (ed.) 9th IMA International Conference on Cryptography and Coding (2003)). In this paper we discuss analogous results for the case of multisequences. We also present improved bounds on the error linear complexity and on the number of sequences satisfying such bounds for the case of single sequences.     

Error linear complexity measures for multisequences

Complexity measures for sequences over finite fields, such as the linear complexity and the k-error linear complexity, play an important role in cryptology. Recent developments in stream ciphers point towards an interest in word-based stream ciphers, which require the study of the complexity of multisequences. We introduce various options for error linear complexity measures for multisequences. For finite multisequences as well as for periodic multisequences with prime period, we present formulas for the number of multisequences with given error linear complexity for several cases, and we present lower bounds for the expected error linear complexity.     

Large families of pseudo-random subsets formed by generalized cyclotomic classes

Recently, Dartyge and Sárközy defined the measures, i.e., the well- distribution measure and the correlation measure of order k, of pseudo-randomness of subsets of the set {1, 2, . . . , N}, and they presented several examples for subsets with strong pseudo-random properties when N is a prime number. In this article, we present a construction of pseudo-random subsets for N = pq and give some partial results on the pseudo-random measures.     

On linear complexity of binary lattices,II

The linear complexity is an important and frequently used measure of unpredictably and pseudorandomness of binary sequences. In Part I of this paper, we extended this notion to two dimensions: we defined and studied the linear complexity of binary and bit lattices. In this paper, first we will estimate the linear complexity of a truly random bit (M,N)-lattice. Next we will extend the notion of k-error linear complexity to bit lattices. Finally, we will present another alternative definition of linear complexity of bit lattices.     

Measures of pseudorandomness for binary sequences constructed using finite fields

We extend the results of Goubin, Mauduit and Sárközy on the well-distribution measure and the correlation measure of order k of the sequence of Legendre sequences with polynomial argument in several ways. We analyze sequences of quadratic characters of finite fields of prime power order and consider in each case two, in general, different definitions of well-distribution measure and correlation measure of order k, respectively.     

A technique to study the correlation measures of binary sequences

Let E^N=(e₁,e₂,…,e_N) be a binary sequence with e_i∈{+1,−1}. For 2≤k≤N, the correlation measure of order k of the sequence is defined by Mauduit and Sárközy as

     

Outlets of 2D invasion percolation and multiple-armed incipient infinite clusters

We study invasion percolation in two dimensions, focusing on properties of the outlets of the invasion and their relation to critical percolation and to incipient infinite clusters (IICs). First we compute the exact decay rate of the distribution of both the weight of the kth outlet and the volume of the kth pond. Next we prove bounds for all moments of the distribution of the number of outlets in an annulus. This result leads to almost sure bounds for the number of outlets in a box B(2 ⁿ ) and for the decay rate of the weight of the kth outlet to p _c . We then prove existence of multiple-armed IIC measures for any number of arms and for any color sequence which is alternating or monochromatic. We use these measures to study the invaded region near outlets and near edges in the invasion backbone far from the origin.     

Betti numbers of finitely presented groups and very rapidly growing functions

Define the length of a finite presentation of a group G as the sum of lengths of all relators plus the number of generators. How large can the kth Betti number b_k(G)= rank H_k(G) be providing that G has length ≤N and b_k(G) is finite? We prove that for every k≥3 the maximum b_k(N) of the kth Betti numbers of all such groups is an extremely rapidly growing function of N. It grows faster that all functions previously encountered in mathematics (outside of logic) including non-computable functions (at least those that are known to us). More formally, b_k grows as the third busy beaver function that measures the maximal productivity of Turing machines with ≤N states that use the oracle for the halting problem of Turing machines using the oracle for the halting problem of usual Turing machines.We also describe the fastest possible growth of a sequence of finite Betti numbers of a finitely presented group. In particular, it cannot grow as fast as the third busy beaver function but can grow faster than the second busy beaver function that measures the maximal productivity of Turing machines using an oracle for the halting problem for usual Turing machines. We describe a natural problem about Betti numbers of finitely presented groups such that its answer is expressed by a function that grows as the fifth busy beaver function.Also, we outline a construction of a finitely presented group all of whose homology groups are either or trivial such that its Betti numbers form a random binary sequence.     

Total palindrome complexity of finite words

The palindrome complexity function pal_w of a word w attaches to each n∈N the number of palindromes (factors equal to their mirror images) of length n contained in w. The number of all the nonempty palindromes in a finite word is called the total palindrome complexity of that word. We present exact bounds for the total palindrome complexity and construct words which have any palindrome complexity between these bounds, for binary alphabets as well as for alphabets with the cardinal greater than 2. Denoting by M_q(n) the average number of palindromes in all words of length n over an alphabet with q letters, we present an upper bound for M_q(n) and prove that the limit of M_q(n)/n is 0. A more elaborate estimation leads to .     

The complexity of detecting fixed-density clusters

We study the complexity of finding a subgraph of a certain size and a certain density, where density is measured by the average degree. Let γ:N→Q₊ be any density function, i.e., γ is computable in polynomial time and satisfies γ(k)?k-1 for all k∈N. Then γ-CLUSTER is the problem of deciding, given an undirected graph G and a natural number k, whether there is a subgraph of G on k vertices that has average degree at least γ(k). For γ(k)=k-1, this problem is the same as the well-known CLIQUE problem, and thus NP-complete. In contrast to this, the problem is known to be solvable in polynomial time for γ(k)=2. We ask for the possible functions γ such that γ-CLUSTER remains NP-complete or becomes solvable in polynomial time. We show a rather sharp boundary: γ CLUSTER is NP-complete if γ=2+Ω(1/k^1-ε) for some ε>0 and has a polynomial-time algorithm for γ=2+O(1/k). The algorithm also shows that for γ=2+O(1/k^1-o(1)), γ-CLUSTER is solvable in subexponential time 2^no(1).     

Asymptotic analysis on the normalized <Emphasis Type="Italic">k</Emphasis>-error linear complexity of binary sequences

Linear complexity and k-error linear complexity are the important measures for sequences in stream ciphers. This paper discusses the asymptotic behavior of the normalized k-error linear complexity \({L_{n,k}(\underline{s})/n}\) of random binary sequences \({\underline{s}}\) , which is based on one of Niederreiter’s open problems. For k = n θ, where 0 ≤ θ ≤ 1/2 is a fixed ratio, the lower and upper bounds on accumulation points of \({L_{n,k}(\underline{s})/n}\) are derived, which holds with probability 1. On the other hand, for any fixed k it is shown that \({\lim_{n\rightarrow\infty} L_{n,k}(\underline{s})/n = 1/2}\) holds with probability 1. The asymptotic bounds on the expected value of normalized k-error linear complexity of binary sequences are also presented.     

Compositional complexity of Boolean functions

We define two measures, γ and c, of complexity for Boolean functions. These measures are related to issues of functional decomposition which (for continuous functions) were studied by Arnol'd, Kolmogorov, Vitu?kin and others in connection with Hilbert's 13th Problem. This perspective was first applied to Boolean functions in [1]. Our complexity measures differ from those which were considered earlier [3, 5, 6, 9, 10] and which were used by Ehrenfeucht and others to demonstrate the great complexity of most decision procedures. In contrast to other measures, both γ and c (which range between 0 and 1) have a more combinatorial flavor and it is easy to show that both of them are close to 0 for literally all “meaningful” Boolean functions of many variables. It is not trivial to prove that there exist functions for which c is close to 1, and for γ the same question is still open. The same problem for all traditional measures of complexity is easily resolved by statistical considerations.     

Topological complexity, fibrations and symmetry

We show how locally smooth actions of compact Lie groups on a manifold X can be used to obtain new upper bounds for the topological complexity TC(X), in the sense of Farber. We also obtain new bounds for the topological complexity of finitely generated torsion-free nilpotent groups.     

Large families of pseudo-random subsets formed by generalized cyclotomic classes

Recently, Dartyge and Sárk?zy defined the measures, i.e., the well- distribution measure and the correlation measure of order k, of pseudo-randomness of subsets of the set {1, 2, . . . , N}, and they presented several examples for subsets with strong pseudo-random properties when N is a prime number. In this article, we present a construction of pseudo-random subsets for N = pq and give some partial results on the pseudo-random measures.     

Linear Complexity,k-Error Linear Complexity,and the Discrete Fourier Transform

Complexity measures for sequences of elements of a finite field play an important role in cryptology. We focus first on the linear complexity of periodic sequences. By means of the discrete Fourier transform, we determine the number of periodic sequences S with given prime period length N and linear complexity L_N, 0(S)=c as well as the expected value of the linear complexity of N-periodic sequences. Cryptographically strong sequences should not only have a large linear complexity, but also the change of a few terms should not cause a significant decrease of the linear complexity. This requirement leads to the concept of the k-error linear complexity L_N, k(S) of sequences S with period length N. For some k and c we determine the number of periodic sequences S with given period length N and L_N, k(S)=c. For prime N we establish a lower bound on the expected value of the k-error linear complexity.     

Multiplicative character sums of Fermat quotients and pseudorandom sequences

We prove a bound on sums of products of multiplicative characters of shifted Fermat quotients modulo p. From this bound we derive results on the pseudorandomness of sequences of modular discrete logarithms of Fermat quotients modulo p: bounds on the well-distribution measure, the correlation measure of order ?, and the linear complexity.     

Large entropy measures for endomorphisms of ℂℙ k

Let f be a holomorphic endomorphism of ?? ^k . We construct by using coding techniques a class of ergodic measures as limits of non-uniform probability measures on preimages of points. We show that they have large metric entropy, close to log d ^k . We establish for them strong stochastic properties and prove the positivity of their Lyapunov exponents. Since they have large entropy, those measures are supported in the support of the maximal entropy measure of f. They in particular provide lower bounds for the Hausdorff dimension of the Julia set.     

On the 16th Hilbert problem for limit cycles on nonsingular algebraic curves

We give an upper bound for the maximum number N of algebraic limit cycles that a planar polynomial vector field of degree n can exhibit if the vector field has exactly k nonsingular irreducible invariant algebraic curves. Additionally we provide sufficient conditions in order that all the algebraic limit cycles are hyperbolic. We also provide lower bounds for N.     

Sums and differences of four <Emphasis Type="Italic">k</Emphasis>th powers

We prove an upper bound for the number of representations of a positive integer N as the sum of four kth powers of integers of size at most B, using a new version of the determinant method developed by Heath-Brown, along with recent results by Salberger on the density of integral points on affine surfaces. More generally we consider representations by any integral diagonal form. The upper bound has the form \({O_{N}(B^{c/\sqrt{k}})}\), whereas earlier versions of the determinant method would produce an exponent for B of order k ^?1/3 (uniformly in N) in this case. Furthermore, we prove that the number of representations of a positive integer N as a sum of four kth powers of non-negative integers is at most \({O_{\varepsilon}(N^{1/k+2/k^{3/2}+\varepsilon})}\) for k ≥ 3, improving upon bounds by Wisdom.     

The expectation and variance of the joint linear complexity of random periodic multisequences

The linear complexity of sequences is one of the important security measures for stream cipher systems. Recently, in the study of vectorized stream cipher systems, the joint linear complexity of multisequences has been investigated. By using the generalized discrete Fourier transform for multisequences, Meidl and Niederreiter determined the expectation of the joint linear complexity of random N-periodic multisequences explicitly. In this paper, we study the expectation and variance of the joint linear complexity of random periodic multisequences. Several new lower bounds on the expectation of the joint linear complexity of random periodic multisequences are given. These new lower bounds improve on the previously known lower bounds on the expectation of the joint linear complexity of random periodic multisequences. By further developing the method of Meidl and Niederreiter, we derive a general formula and a general upper bound for the variance of the joint linear complexity of random N-periodic multisequences. These results generalize the formula and upper bound of Dai and Yang for the variance of the linear complexity of random periodic sequences. Moreover, we determine the variance of the joint linear complexity of random periodic multisequences with certain periods.