On finite pseudorandom lattices of k symbols

In earlier papers Mauduit and Sárközy have introduced and studied the measures of pseudorandomness for finite binary sequences and sequences of k symbols. Later they (with further coauthors) extended the notation of binary sequences to binary lattices. In this paper measures of pseudorandom lattices of k symbols are introduced and studied for “truly random” lattices.     

Extension of the notion of collision and avalanche effect to sequences of k symbols

In recent papers [14], [15] I studied collision and avalanche effect in families of finite pseudorandom binary sequences. Motivated by applications, Mauduit and Sárk?zy in [13] generalized and extended this theory from the binary case to k-ary sequences, i.e., to k symbols. They constructed a large family of k-ary sequences with strong pseudorandom properties. In this paper our goal is to extend the study of the pseudorandom properties mentioned above to k-ary sequences. The aim of this paper is twofold. First we will extend the definitions of collision and avalanche effect to k-ary sequences, and then we will study these related properties in a large family of pseudorandom k-ary sequences with ??small?? pseudorandom measures.     

Proof of the conjectures of Bernstein and Erdös concerning the optimal nodes for polynomial interpolation

Convergence properties of sequences of continuous functions, with kth order divided differences bounded from above or below, are studied. It is found that for such sequences, convergence in a “monotone norm” (e.g., L_p) on [a, b] to a continuous function implies uniform convergence of the sequence and its derivatives up to order k ? 1 (whenever they exist), in any closed subinterval of [a, b]. Uniform convergence in the closed interval [a, b] follows from the boundedness from below and above of the kth order divided differences. These results are applied to the estimation of the degree of approximation in Monotone and Restricted Derivative approximation, via bounds for the same problems with only one restricted derivative.     

A note on random k-dimensional posets

In 2009, Janson [Poset limits and exchangeable random posets, Institut Mittag-Leffler preprint, 36pp, arXiv:0902.0306] extended the recent theory of graph limits to posets, defining convergence for poset sequences and proving that every such sequence has a limit object. In this paper, we focus on k-dimensional poset sequences. This restriction leads to shorter proofs and to a more intuitive limit object. As before, the limit object can be used as a model for random posets, which generalizes the well known random k-dimensional poset model. This investigation also leads to a definition of quasirandomness for k-dimensional posets, which can be captured by a natural distance that measures the discrepancy of a k-dimensional poset.     

Syzygy and Torsionless Modules with Respect to a Semidualizing Module

This paper aims at generalizing the notions of “Auslander dual”, “k-torsionless” and “k-th syzygy” modules to the relative setting with respect to a semidualizing module. It is shown that the “relative” Auslander dual shares many nice properties with the Auslander dual originally introduced by Auslander and Bridger. It is also shown the interplay between the “relative” version of “k-torsionless” and “k-th syzygy” modules parallels that of k-torsionless and k-th syzygy modules.     

Construction of pseudorandom binary sequences using additive characters over GF(2<Superscript><Emphasis Type="Italic">k</Emphasis></Superscript>) II

In a series of papers Mauduit and Sárközy introduced measures of pseudorandomness and they constructed large families of sequences with strong pseudorandom properties. In later papers the structure of families of binary sequences was also studied. In these constructions fields with prime order were used. Throughout this paper the structure of a family of binary sequences based on GF(2 ^k ) will be studied.     

Properties of locally convergent sequences with respect to median filter

In this paper, for infinite-length sequences (or sequences), we prove that a sequence is convergent with respect to the median filter with window width 2k+1 if and only if the sequence is locally convergent on a segment of length 2k−1 in the sequence. Moreover, the length 2k−1 is minimal for k≠2,3.     

On Woodall's interval problem

For each k > 1, a sequence of 4(k ? 1) ? [log₂ (k ? 1)] sets (layers) of disjoint intervals in $\text{R}$ is constructed, such that every interval overlaps at least one interval in each preceding layer and no point of $\text{R}$ belongs to more than k layers. This improves a construction of Woodall. The approach is by way of the related “saturation” or “scope” problem.     

A factorization theorem for a certain class of graphs

In this note we give a necessary and sufficient condition for factorization of graphs satisfying the “odd cycle property”. We show that a graph G with the odd cycle property contains a [k_i] factor if and only if the sequence [H]+[k_i] is graphical for all subgraphs H of the complement of G.A similar theorem is shown to be true for all digraphs.     

Gray codes in graphs of subsets

Let G(n,k) be a graph whose vertices are the k-element subsets of an n-set represented as n-tuples of “O's” and “1's” with k “1's”. Two such subsets are adjacent if one can be obtained from the other by switching a “O” and a “1” which are in adjacent positions, where the first and nth positions are also considered adjacent. The problem of finding hamiltonian cycles in G(n,k) is discussed. This may be considered a problem of finding “Gray codes” of the k-element subsets of an n-set. It is shown that no such cycle exists if n and k are both even or if k=2 and n?7 and that such a cycle does exist in all other cases where k?5.     

A gradual rank increasing process for matrix completion

The matrix completion problem is easy to state: let A be a given data matrix in which some entries are unknown. Then, it is needed to assign “appropriate values” to these entries. A common way to solve this problem is to compute a rank-k matrix, B _k , that approximates A in a least squares sense. Then, the unknown entries in A attain the values of the corresponding entries in B _k . This raises the question of how to determine a suitable matrix rank. The method proposed in this paper attempts to answer this question. It builds a finite sequence of matrices \(B_{k}, k = 1, 2, \dots \), where B _k is a rank-k matrix that approximates A in a least squares sense. The computational effort is reduced by using B _k-1 as starting point in the computation of B _k . The ability of B _k to serve as substitute for A is measured with two objective functions: a “training” function that measures the distance between the known part of A and the corresponding part of B _k , and a “probe” function that assesses the quality of the imputed entries. Watching the changes in these functions as k increases enables us to find an optimal matrix rank. Numerical experiments illustrate the usefulness of the proposed approach.     

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.     

A case of Toeplitz determinants and theta functions in frequency analysis

For a trigonometric signal an important problem is to find the unknown frequencies from a set of observations. This is called the frequency analysis problem.One method is to construct, from measured values, a family of positive measures, depending upon one or more parameters. These define in turn an inner product, positive definite sequences of moments, and sequences of polynomials (or more generally rational functions), orthogonal on the unit circle. Asymptotic properties of the zeros then lead to the frequencies.In recent variations of this method the moments are modified. If the new sequence also is positive definite we are back to the method just mentioned. But sometimes it is difficult to find out if it is positive definite or not.A “strange-looking” modification, multiplication of the “moments” by Rⁿ² where R∈(0,1) was introduced very recently. This modification turned out to be rewarding in different surprising ways in all examples carried out, although at first the question of positive definiteness was unsettled. In the present paper, the positive definiteness is proved. Moreover, it is proved that for α>2 multiplication by R^|n|α does not generally lead to a positive definite sequence     

Irregular discrepancy behavior of lacunary series II

In 1975 Philipp proved the following law of the iterated logarithm (LIL) for the discrepancy of lacunary series: let (n _k ) _{k ≥ 1} be a lacunary sequence of positive integers, i.e. a sequence satisfying the Hadamard gap condition n _k+1/n _k > q > 1. Then ${1/(4 \sqrt{2}) \leq \limsup_{N \to \infty} N D_N(n_k x) (2 N \log \log N)^{-1/2}\leq C_q}$ for almost all ${x \in (0,1)}$ in the sense of Lebesgue measure. The same result holds, if the “extremal discrepancy” D _N is replaced by the “star discrepancy” ${D_N^*}$ . It has been a long standing open problem whether the value of the limsup in the LIL has to be a constant almost everywhere or not. In a preceding paper we constructed a lacunary sequence of integers, for which the value of the limsup in the LIL for the star discrepancy is not a constant a.e. Now, using a refined version of our methods from this preceding paper, we finally construct a sequence for which also the value of the limsup in the LIL for the extremal discrepancy is not a constant a.e.     

On condition numbers of the Shanks transformation

Quasi-linear functions generate sequence transformation methods whose conditioning depends upon the nature of the sequence to be accelerated. These methods are often well conditioned when they are applied to alternating sequences; however, they are relatively ill-conditioned in case of monotonic convergence. The condition numbers of the Shanks transformation e_k(s_n) are given in order to prove that the closely related ε-algorithm to a such transformation is ill-conditioned when performed on the set of totally monotonic sequences. In the same way, we show that this algorithm is well conditioned on the set of totally oscillating sequences.     

The k–Fibonacci difference sequences

In this paper we apply the concept of difference relation to the sequences of k–Fibonacci numbers. We will obtain general formulas to find any term of the ith k–Fibonacci difference sequence from the initial k–Fibonacci numbers. We also find formulas for the sum of the elements of these new sequences as well as their generating functions. Finally, we study the k–Fibonacci Newton polynomial interpolation.     

Upper bounds on the length of a shortest closed geodesic and quantitative Hurewicz theorem

In this paper we present two upper bounds on the length of a shortest closed geodesic on compact Riemannian manifolds. The first upper bound depends on an upper bound on sectional curvature and an upper bound on the volume of the manifold. The second upper bound will be given in terms of a lower bound on sectional curvature, an upper bound on the diameter and a lower bound on the volume.The related questions that will also be studied are the following: given a contractible k-dimensional sphere in M ⁿ , how “fast” can this sphere be contracted to a point, if π _i (M ⁿ )={0} for 1≤i<k. That is, what is the maximal length of the trajectory described by a point of a sphere under an “optimal” homotopy? Also, what is the “size” of the smallest non-contractible k-dimensional sphere in a (k-1)-connected manifold M ⁿ providing that M ⁿ is not k-connected?     

Homological properties of piecewise hereditary algebras

Let Λ be a finite dimensional algebra over an algebraically closed field k. We will investigate homological properties of piecewise hereditary algebras Λ. In particular we give lower and upper bounds of the strong global dimension, show the behavior of the strong global dimension under one point extensions and tilting. Moreover we show that the “pieces” of modΛ have Auslander–Reiten sequences.     

Correlation measure,linear complexity and maximum order complexity for families of binary sequences

The correlation measure of order k is an important measure of pseudorandomness for binary sequences. This measure tries to look for dependence between several shifted versions of a sequence. We study the relation between the correlation measure of order k and two other pseudorandom measures: the Nth linear complexity and the Nth maximum order complexity. We simplify and improve several state-of-the-art lower bounds for these two measures using the Hamming bound as well as weaker bounds derived from it.     

Chromatic number and skewness

In this note, we solve the problem of determing the chromatic number of planar graphs to which a certain number μ of “extra” edges are attached. We obtain a (best-possible) theorem when μ < ₂^k for every integer k ≥ 3. The statement of the theorem for k = 2 is the Four-Color Conjecture.