Everywhere -repetitive sequences and Sturmian words

Local constraints on an infinite sequence that imply global regularity are of general interest in combinatorics on words. We consider this topic by studying everywhere α-repetitive sequences. Such a sequence is defined by the property that there exists an integer N≥2 such that every length-N factor has a repetition of order α as a prefix. If each repetition is of order strictly larger than α, then the sequence is called everywhere α⁺-repetitive. In both cases, the number of distinct minimal α-repetitions (or α⁺-repetitions) occurring in the sequence is finite.A natural question regarding global regularity is to determine the least number, denoted by M(α), of distinct minimalα-repetitions such that an α-repetitive sequence is not necessarily ultimately periodic. We call the everywhere α-repetitive sequences witnessing this property optimal. In this paper, we study optimal 2-repetitive sequences and optimal 2⁺-repetitive sequences, and show that Sturmian words belong to both classes. We also give a characterization of 2-repetitive sequences and solve the values of M(α) for 1≤α≤15/7.     

Algebraic Approaches to Periodic Arithmetical Maps

A residue class a + n with weight λ is denoted by λ, a, n. For a finite system = {λ_s, a_s, n_s}^k_{s = 1} of such triples, the periodic map w (x) = ∑_{ns|x − as} λ_s is called the covering map of . Some interesting identities for those with a fixed covering map have been known; in this paper we mainly determine all those functions f : Ω → such that ∑^k_{s = 1} λ_sf(a_s + n_s ) depends only on w where Ω denotes the family of all residue classes. We also study algebraic structures related to such maps f, and periods of arithmetical functions ψ(x) = ∑^k_{s = 1} λ_se^2πia_sx/n_s and ω(x) = |{1 ≤ s ≤ k : (x + a_s, n_s) = 1}|.     

Periodic points for onto cellular automata

Let φ be a one-dimensional surjective cellular automaton map. We prove that if φ is a closing map, then the configurations which are both spatially and temporally periodic are dense. (If φ is not a closing map, then we do not know whether the temporally periodic configurations must be dense.) The results are special cases of results for shifts of finite type, and the proofs use symbolic dynamical techniques.     

Decision problems for inverse monoids presented by a single sparse relator

We study a class of inverse monoids of the form M=Inv 〈X∣w=1〉, where the single relator w has a combinatorial property that we call sparse. For a sparse word w, we prove that the word problem for M is decidable. We also show that the set of words in (X∪X ⁻¹)^* that represent the identity in M is a deterministic context free language, and that the set of geodesics in the Schützenberger graph of the identity of M is a regular language.     

The generalized variance of a stationary autoregressive process

For a stationary autoregressive process of order p and disturbance variance σ² it is shown that the determinant of the covariance of T (≥p) consecutive random variables of the process is (σ²)^T Π_i,j=1^p (1 − w_iw_j)⁻¹, where w₁, …, w_p are the roots of the associated polynomial equation.     

Bit-parallel -matching and suffix automata

(δ,γ)-matching is a string matching problem with applications to music retrieval. The goal is, given a pattern P_1…m and a text T_1…n on an alphabet of integers, find the occurrences P^′ of the pattern in the text such that (i) , and (ii) . The problem makes sense for δγδm. Several techniques for (δ,γ)-matching have been proposed, based on bit-parallelism or on skipping characters. We first present an O(mnlog(γ)/w) worst-case time and O(n) average-case time bit-parallel algorithm (being w the number of bits in the computer word). It improves the previous O(mnlog(δm)/w) worst-case time algorithm of the same type. Second, we combine our bit-parallel algorithm with suffix automata to obtain the first algorithm that skips characters using both δ and γ. This algorithm examines less characters than any previous approach, as the others do just δ-matching and check the γ-condition on the candidates. We implemented our algorithms and drew experimental results on real music, showing that our algorithms are superior to current alternatives with high values of δ.     

A generalization of the Weinstein-Moser theorems on periodic orbits of a Hamiltonian system near an equilibrium

We study the Hamiltonian system (HS) where H ε C² ( ^2N, ) satisfies H (0) = 0, H′ (0) = 0 and the quadratic form ) is non-degenerate. We fix τ₀ > 0 and assume that ²N E F decomposes into linear subspaces E and F which are invariant under the flow associated to the linearized system (LHS) = JH″ (0) x and such that each solution of (LHS) in E is τ₀-periodic whereas no solution of (LHS) in F − 0 is τ₀-periodic. We write σ(τ₀) = σ_Q(τ₀) for the signature of the quadratic form Q restricted to E. If σ(τ₀) ≠ 0 then there exist periodic solutions of (HS) arbitrarily close to 0. More precisely we show, either there exists a sequence x_k → 0 of τ_k-periodic orbits on the energy level H⁻¹ (0) with τ_k → τ₀; or for each λ close to 0 with λσ(τ₀) > 0 the energy level H⁻¹ (λ) contains at least distinct periodic orbits of (HS) near 0 with periods near τ₀. This generalizes a result of Weinstein and Moser who assumed QE to be positive definite.     

Periodic and Homoclinic Solutions of Extended Fisher–Kolmogorov Equations

In this paper we study the existence of periodic solutions of the fourth-order equations u^iv − pu″ − a(x)u + b(x)u³ = 0 and u^iv − pu″ + a(x)u − b(x)u³ = 0, where p is a positive constant, and a(x) and b(x) are continuous positive 2L-periodic functions. The boundary value problems (P₁) and (P₂) for these equations are considered respectively with the boundary conditions u(0) = u(L) = u″(0) = u″(L) = 0. Existence of nontrivial solutions for (P₁) is proved using a minimization theorem and a multiplicity result using Clark's theorem. Existence of nontrivial solutions for (P₂) is proved using the symmetric mountain-pass theorem. We study also the homoclinic solutions for the fourth-order equation u^iv + pu″ + a(x)u − b(x)u² − c(x)u³ = 0, where p is a constant, and a(x), b(x), and c(x) are periodic functions. The mountain-pass theorem of Brezis and Nirenberg and concentration-compactness arguments are used.     

On minimal Sturmian partial words

Partial words, which are sequences that may have some undefined positions called holes, can be viewed as sequences over an extended alphabet A_?=A∪{?}, where ? stands for a hole and matches (or is compatible with) every letter in A. The subword complexity of a partial word w, denoted by p_w(n), is the number of distinct full words (those without holes) over the alphabet that are compatible with factors of length n of w. A function f:N→N is (k,h)-feasible if for each integer N≥1, there exists a k-ary partial word w with h holes such that p_w(n)=f(n) for all n such that 1≤n≤N. We show that when dealing with feasibility in the context of finite binary partial words, the only affine functions that need investigation are f(n)=n+1 and f(n)=2n. It turns out that both are (2,h)-feasible for all non-negative integers h. We classify all minimal partial words with h holes of order N with respect to f(n)=n+1, called Sturmian, computing their lengths as well as their numbers, except when h=0 in which case we describe an algorithm that generates all minimal Sturmian full words. We show that up to reversal and complement, any minimal Sturmian partial word with one hole is of the form aⁱ?a^jba^l, where i,j,l are integers satisfying some restrictions, that all minimal Sturmian partial words with two holes are one-periodic, and that up to complement, ?(a^N−1?)^h−1 is the only minimal Sturmian partial word with h≥3 holes. Finally, we give upper bounds on the lengths of minimal partial words with respect to f(n)=2n, showing them tight for h=0,1 or 2.     

Morse and Hedlund’s Skew Sturmian Words Revisited

For any infinite word r over A = {a, b} we associate two infinite words min(r), max(r) such that any prefix of min(r) (max(r), respectively) is the lexicographically smallest (greatest, respectively) among the factors of r of the same length. We prove that (min(r); max(r)) = (as, bs) for some infinite word s if and only if r is a proper Sturmian word or an ultimately periodic word of a particular form. This result is based on a lemma concerning sequences of infinite words. Received July 11, 2005     

Approximation of elements of a generalized Orlicz sequence space by nonlinear, singular kernels

Let l be a generalized Orlicz sequence space generated by a modular (x) = ∑_{i − 0}^∞ _i(¦t_i¦), X = (t_i), with s-convex functions _i, 0 < s 1, and let K_w,j: R₊ → R₊ for j=0,1,2,…, w ε Wwhere is an abstract set of indices. Assuming certain singularity assumptions on the nonlinear kernel K_w,j and setting T_wx = ((T_wx)_i)_{i = 0}^∞, with (T_wx)_i = ∑_{j = 0}ⁱ K_{w,i − j}(¦t_j¦) for x = (t_j), convergence results: T_wx → x in l are obtained (both modular convergence and norm convergence), with respect to a filter of subsets of the set .     

The structure of invertible substitutions on a three-letter alphabet

We study the structure of invertible substitutions on three-letter alphabet. We show that there exists a finite set of invertible substitutions such that any invertible substitution can be written as I_wσ₁σ₂σ_k, where I_w is the inner automorphism associated with w, and for 1jk. As a consequence, M is the matrix of an invertible substitution if and only if it is a finite product of non-negative elementary matrices.     

Littlewood–Paley and Multiplier Theorems on Weighted Spaces over Locally Compact Vilenkin Groups

We extend the Littlewood–Paley theorem toL^p_w(G), whereGis a locally compact Vilenkin group andware weights satisfying the MuckenhouptA_pcondition. As an application we obtain a mixed-norm type multiplier result onL^p_w(G) and prove the sharpness of our result. We also obtain a sufficient condition for φ L^∞(Γ) to be a multiplier on the power weightedL^p_α(G) in terms of its smoothness condition.     

On the infinite permutation generated by the period doubling word

The paper is devoted to the properties of infinite permutations. We introduce the infinite permutation ξ, in some sense similar to the period doubling word w (which is the fixed point of the morphism φ_w:00100,10101). We investigate combinatorial properties of ξ and find the complexity of ξ.     

Consistency of a recursive nearest neighbor regression function estimate

Let (X, Y) be an ^d × -valued random vector and let (X₁, Y₁),…,(X_N, Y_N) be a random sample drawn from its distribution. Divide the data sequence into disjoint blocks of length l₁, …, l_n, find the nearest neighbor to X in each block and call the corresponding couple (X_i^*, Y_i^*). It is shown that the estimate m_n(X) = Σ_{i = 1}ⁿ w_niY_i^*/Σ_{i = 1}ⁿ w_ni of m(X) = E{Y|X} satisfies E{|m_n(X) − m(X)|^p} 0 (p ≥ 1) whenever E{|Y|^p} < ∞, l_n ∞, and the triangular array of positive weights {w_ni} satisfies sup_{i ≤ n}w_ni/Σ_{i = 1}ⁿ w_ni 0. No other restrictions are put on the distribution of (X, Y). Also, some distribution-free results for the strong convergence of E{|m_n(X) − m(X)|^p|X₁, Y₁,…, X_N, Y_N} to zero are included. Finally, an application to the discrimination problem is considered, and a discrimination rule is exhibited and shown to be strongly Bayes risk consistent for all distributions.     

Quadrature rules using first derivatives for oscillatory integrands

We consider the integral of a function and its approximation by a quadrature rule of the form

i.e., by a rule which uses the values of both y and its derivative at nodes of the quadrature rule. We examine the cases when the integrand is either a smooth function or an ω dependent function of the form y(x)=f₁(x) sin(ωx)+f₂(x) cos(ωx) with smoothly varying f₁ and f₂. In the latter case, the weights w_k and α_k are ω dependent. We establish some general properties of the weights and present some numerical illustrations.     

On weighted Lebesgue function type sums

Let I be a finite or infinite interval and dμ a measure on I. Assume that the weight function w(x)>0, w^′(x) exists, and the function w^′(x)/w(x) is non-increasing on I. Denote by ℓ_k's the fundamental polynomials of Lagrange interpolation on a set of nodes x₁<x₂<<x_n in I. The weighted Lebesgue function type sum for 1≤i<j≤n and s≥1 is defined by

In this paper the exact lower bounds of S_n(x) on a “big set” of I and are obtained. Some applications are also given.     

On the existence of the best discrete approximation in norm by reciprocals of real polynomials

For the given data (w_i,x_i,y_i), i=1,…,M, we consider the problem of existence of the best discrete approximation in l_p norm (1≤p<∞) by reciprocals of real polynomials. For this problem, the existence of best approximations is not always guaranteed. In this paper, we give a condition on data which is necessary and sufficient for the existence of the best approximation in l_p norm. This condition is theoretical in nature. We apply it to obtain several other existence theorems very useful in practice. Some illustrative examples are also included.     

Wiener-Hopf Operators with Semi-almost Periodic Matrix Symbols on Weighted Lebesgue Spaces

Fredholm criteria and index formulas are established for Wiener-Hopf operators W(a) with semi-almost periodic matrix symbols a on weighted Lebesgue spaces where 1 < p < ∞, w belongs to a subclass of Muckenhoupt weights and . We also study the invertibility of Wiener-Hopf operators with almost periodic matrix symbols on . In the case N = 1 we also obtain a semi-Fredholm criterion for Wiener-Hopf operators with semi-almost periodic symbols and, for another subclass of weights, a Fredholm criterion for Wiener-Hopf operators with semi-periodic symbols. Work was supported by the SEP-CONACYT Project No. 25564 (México). The second author was also sponsored by the CONACYT scholarship No. 163480.     

Finitely Correlated Pure States

We study a w*-dense subset of the translation invariant states on an infinite tensor product algebra , where is a matrix algebra. These "finitely correlated states" are explicitly constructed in terms of a finite dimensional auxiliary algebra and a completely positive map : → . We show that such a state ω is pure if and only if it is extremal periodic and its entropy density vanishes. In this case the auxiliary objects and are uniquely determined by ω, and can be expressed in terms of an isometry between suitable tensor product Hilbert spaces.