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.     

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.     

Multisequences with large linear and k-error linear complexity from a tower of Artin–Schreier extensions of function fields

In this paper, we construct multisequences with both large (joint) linear complexity and k-error (joint) linear complexity from a tower of Artin–Schreier extensions of function fields. Moreover, these sequences can be explicitly constructed.     

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.     

On the condensation points of the lagrange spectrum

For a positive integerN, L(N) denotes the set of Lagrange values of all sequences (a _k:k=0, ±1, ±2,…) of positive integers with lim sup _k ^ak=N. It is shown that for anyN≥3L(N) has infinitely many condensation points. Such points can be realized as Markov values of symmetric doubly periodic sequences whose period consists of a semi-symmetric tuple.     

The k-error linear complexity distribution for 2^n-periodic binary sequences

The linear complexity and the \(k\) -error linear complexity of a sequence have been used as important security measures for key stream sequence strength in linear feedback shift register design. By using the sieve method of combinatorics, we investigate the \(k\) -error linear complexity distribution of \(2^n\) -periodic binary sequences in this paper based on Games–Chan algorithm. First, for \(k=2,3\) , the complete counting functions for the \(k\) -error linear complexity of \(2^n\) -periodic binary sequences (with linear complexity less than \(2^n\) ) are characterized. Second, for \(k=3,4\) , the complete counting functions for the \(k\) -error linear complexity of \(2^n\) -periodic binary sequences with linear complexity \(2^n\) are presented. Third, as a consequence of these results, the counting functions for the number of \(2^n\) -periodic binary sequences with the \(k\) -error linear complexity for \(k = 2\) and \(3\) are obtained.     

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 .      

Existence of extremal metrics on almost homogeneous manifolds of cohomogeneity one —IV

This paper is the first of a series of papers in which we generalize our results in (Asian J. of Math. 4, 817–830 (2000); J. Geom. Anal. 12, 63–79 (2002); Intern. J. Math. 14, 259–287 (2003)) to the general complex compact almost homogeneous manifolds of real cohomogeneity one. In this paper we deal with the exceptional case of the G ₂ action (Cf. Intern. J. Math. 14, 259–287 (2003), p. 285). In particular, we prove the existence of Kähler-Einstein metric on this manifold.     

The size of sums of sets,II

We prove inequalities which give lower bounds for the Lebesgue measures of setsE +K whereK is a certain kind of Cantor set. For example, ifC is the Cantor middle-thirds subset of the circle groupT, then $$m(E)^{1 - log2/log3} \leqq m(E + C)$$ for every BorelE ?T.     

Strong convergence theorems for strictly asymptotically pseudocontractive mappings in Hilbert spaces

The purpose of this paper is by using CSQ method to study the strong convergence problem of iterative sequences for a pair of strictly asymptotically pseudocontractive mappings to approximate a common fixed point in a Hilbert space. Under suitable conditions some strong convergence theorems are proved. The results presented in the paper are new which extend and improve some recent results of Acedo and Xu [Iterative methods for strict pseudo-contractions in Hilbert spaces. Nonlinear Anal., 67(7), 2258??271 (2007)], Kim and Xu [Strong convergence of modified Mann iterations for asymptotically nonexpansive mappings and semigroups. Nonlinear Anal., 64, 1140??152 (2006)], Martinez-Yanes and Xu [Strong convergence of the CQ method for fixed point iteration processes. Nonlinear Anal., 64, 2400??411 (2006)], Nakajo and Takahashi [Strong convergence theorems for nonexpansive mappings and nonexpansive semigroups. J. Math. Anal. Appl., 279, 372??79 (2003)], Marino and Xu [Weak and strong convergence theorems for strict pseudocontractions in Hilbert spaces. J. Math. Anal. Appl., 329(1), 336??46 (2007)], Osilike et al. [Demiclosedness principle and convergence theorems for k-strictly asymptotically pseudocontractive maps. J. Math. Anal. Appl., 326, 1334??345 (2007)], Liu [Convergence theorems of the sequence of iterates for asymptotically demicontractive and hemicontractive mappings. Nonlinear Anal., 26(11), 1835??842 (1996)], Osilike et al. [Fixed points of demi-contractive mappings in arbitrary Banach spaces. Panamer Math. J., 12 (2), 77??8 (2002)], Gu [The new composite implicit iteration process with errors for common fixed points of a finite family of strictly pseudocontractive mappings. J. Math. Anal. Appl., 329, 766??76 (2007)].     

Analysis of Basis Pursuit via Capacity Sets

Finding the sparsest solution α for an under-determined linear system of equations D α=s is of interest in many applications. This problem is known to be NP-hard. Recent work studied conditions on the support size of α that allow its recovery using ? ₁-minimization, via the Basis Pursuit algorithm. These conditions are often relying on a scalar property of D called the mutual-coherence. In this work we introduce an alternative set of features of an arbitrarily given D, called the capacity sets. We show how those could be used to analyze the performance of the basis pursuit, leading to improved bounds and predictions of performance. Both theoretical and numerical methods are presented, all using the capacity values, and shown to lead to improved assessments of the basis pursuit success in finding the sparest solution of D α=s.     

Stable Stationary Harmonic Maps to Spheres

For k ≥ 3, we establish new estimate on Hausdorff dimensions of the singular set of stable-stationary harmonic maps to the sphere S^k. We show that the singular set of stable-stationary harmonic maps from B5 to 83 is the union of finitely many isolated singular points and finitely many HSlder continuous curves. We also discuss the minimization problem among continuous maps from B^n to S^2.     

A counterexample concerning the 3-error linear complexity of 2 n -periodic binary sequences

In this article, we present a counterexample to Theorem 4.2 and Theorem 5.2 by Kavuluru (Des Codes Cryptogr 53:75–97, 2009). We conclude that the counting functions for the number of 2 ⁿ -periodic binary sequences with fixed 3-error linear complexity by Kavuluru are not correct.     

On lattice profile of the elliptic curve linear congruential generators

Lattice tests are quality measures for assessing the intrinsic structure of pseudorandom number generators. Recently a new lattice test has been introduced by Niederreiter and Winterhof. In this paper, we present a general inequality that is satisfied by any periodic sequence. Then, we analyze the behavior of the linear congruential generators on elliptic curves (EC-LCG) under this new lattice test and prove that the EC-LCG passes it up to very high dimensions. We also use a result of Brandstätter and Winterhof on the linear complexity profile related to the correlation measure of order $k$ to present lower bounds on the linear complexity profile of some binary sequences derived from the EC-LCG.     

Properties of Integers and Finiteness Conditions for Semigroups

Let h and k be integers greater than 1; we prove that the following statements are equivalent: 1) the direct product of h copies of the additive semigroup of non-negative integers is not k-repetitive; 2) if the direct product of h finitely generated semigroups is k-repetitive, then one of them is finite. Using this and some results of Dekking and Pleasants on infinite words, we prove that certain repetitivity properties are finiteness conditions for finitely generated semigroups.     

Torsion and Abelianization in Equivariant Cohomology

Let X be a topological space upon which a compact connected Lie group G acts. It is well known that the equivariant cohomology H ^* _G (X; Q) is isomorphic to the subalgebra of Weyl group invariants of the equivariant cohomology H ^* _T (X; Q), where T is a maximal torus of G. This relationship breaks down for coefficient rings k other than Q. Instead, we prove that under a mild condition on k the algebra H ^* _G (X; k) is isomorphic to the subalgebra of H ^* _T (X; k) annihilated by the divided difference operators.     

Sets of vectors with many orthogonal paris:

What is the most number of vectors inR ^d such that anyk+1 contain an orthogonal pair? The 24 positive roots of the root systemF ₄ inR ⁴ show that this number could exceeddk.     

On-Line Dimension for Posets Excluding Two Long Incomparable Chains

For a positive integer k, let k?+?k denote the poset consisting of two disjoint k-element chains, with all points of one chain incomparable with all points of the other. Bosek, Krawczyk and Szczypka showed that for each k?≥?1, there exists a constant c _k so that First Fit will use at most $c_kw^2$ chains in partitioning a poset P of width at most w, provided the poset excludes k?+?k as a subposet. This result played a key role in the recent proof by Bosek and Krawczyk that O(w ^16logw ) chains are sufficient to partition on-line a poset of width w into chains. This result was the first improvement in Kierstead’s exponential bound: (5 ^w ???1)/4 in nearly 30 years. Subsequently, Joret and Milans improved the Bosek–Krawczyk–Szczypka bound for the performance of First Fit to 8(k???1)² w, which in turn yields the modest improvement to O(w ^14logw ) for the general on-line chain partitioning result. In this paper, we show that this class of posets admits a notion of on-line dimension. Specifically, we show that when k and w are positive integers, there exists an integer t?=?t(k,w) and an on-line algorithm that will construct an on-line realizer of size t for any poset P having width at most w, provided that the poset excludes k?+?k as a subposet.