Quasi-median hulls in Hamming space are Steiner hulls

A Hamming space Λⁿ consists of all sequences of length n over an alphabet Λ and is endowed with the Hamming distance. In particular, any set of aligned DNA sequences of fixed length constitutes a subspace of a Hamming space with respect to mismatch distance. The quasi-median operation returns for any three sequences u,v,w the sequence which in each coordinate attains either the majority coordinate from u,v,w or else (in the case of a tie) the coordinate of the first entry, u; for a subset of Λⁿ the iterative application of this operation stabilizes in its quasi-median hull. We show that for every finite tree interconnecting a given subset X of Λⁿ there exists a shortest realization within Λⁿ for which all interior nodes belong to the quasi-median hull of X. Hence the quasi-median hull serves as a Steiner hull for the Steiner problem in Hamming space.     

Evolutionary trees and the Ising model on the Bethe lattice: a proof of Steel��s conjecture

A major task of evolutionary biology is the reconstruction of phylogenetic trees from molecular data. The evolutionary model is given by a Markov chain on a tree. Given samples from the leaves of the Markov chain, the goal is to reconstruct the leaf-labelled tree. It is well known that in order to reconstruct a tree on n leaves, sample sequences of length ??(log n) are needed. It was conjectured by Steel that for the CFN/Ising evolutionary model, if the mutation probability on all edges of the tree is less than ${p^{\ast} = (\sqrt{2}-1)/2^{3/2}}$ , then the tree can be recovered from sequences of length O(log n). The value p* is given by the transition point for the extremality of the free Gibbs measure for the Ising model on the binary tree. Steel??s conjecture was proven by the second author in the special case where the tree is ??balanced.?? The second author also proved that if all edges have mutation probability larger than p* then the length needed is n ^??(1). Here we show that Steel??s conjecture holds true for general trees by giving a reconstruction algorithm that recovers the tree from O(log n)-length sequences when the mutation probabilities are discretized and less than p*. Our proof and results demonstrate that extremality of the free Gibbs measure on the infinite binary tree, which has been studied before in probability, statistical physics and computer science, determines how distinguishable are Gibbs measures on finite binary trees.     

Identity theorem for bounded p-adic meromorphic functions

Let K be a complete ultrametric algebraically closed field. We investigate several properties of sequences (an)_n∈N in a disk d(0,R⁻) with regards to bounded analytic functions in that disk: sequences of uniqueness (when f(an)=0∀n∈N implies f=0), identity sequences (when limn→+∞f(an)=0 implies f=0) and analytic boundaries (when lim supn→∞|f(an)|=‖f‖). Particularly, we show that identity sequences and analytic boundary sequences are two equivalent properties. For certain sequences, sequences of uniqueness and identity sequences are two equivalent properties. A connection with Blaschke sequences is made. Most of the properties shown on analytic functions have continuation to meromorphic functions.     

The existence of (p,q)-extended Rosa sequences

A (p,q)-extended Rosa sequence is a sequence of length 2n+2 containing each of the symbols 0,1,…,n exactly twice, and such that two occurrences of the integer j>0 are separated by exactly j-1 symbols. We prove that, with two exceptions, the conditions necessary for the existence of a (p,q)-extended Rosa sequence with prescribed positions of the symbols 0 are sufficient. We also extend the result to λ-fold (p,q)-extended Rosa sequences; i.e., the sequences where every pair of numbers is repeated exactly λ times.     

Julia sets and periodic kneading sequences

We construct abstract Julia sets homeomorphic to Julia sets for complex polynomials of the form f _c (z) = z ² + c, having an associated periodic kneading sequence of the form [`(a*)]{\overline{\alpha\ast}} which is not a period n-tupling. We show that there is a single simply-defined space of “itineraries” which contains homeomorphic copies of all such Julia sets in a natural combinatorial way, with dynamical properties which are derivable directly from the combinatorics. This also leads to a natural definition of abstract Julia sets even for those kneading sequences which are not realized by any polynomial f _c , with similar dynamical properties.     

On the modular sumset partition problem

A sequence m₁≥m₂≥?≥m_k of k positive integers isn-realizable if there is a partition X₁,X₂,…,X_k of the integer interval [1,n] such that the sum of the elements in X_i is m_i for each i=1,2,…,k. We consider the modular version of the problem and, by using the polynomial method by Alon (1999) [2], we prove that all sequences in Z/pZ of length k≤(p−1)/2 are realizable for any prime p≥3. The bound on k is best possible. An extension of this result is applied to give two results of p-realizable sequences in the integers. The first one is an extension, for n a prime, of the best known sufficient condition for n-realizability. The second one shows that, for n≥(4k)³, an n-feasible sequence of length k isn-realizable if and only if it does not contain forbidden subsequences of elements smaller than n, a natural obstruction forn-realizability.     

Higher-dimensional Auslander-Reiten theory on maximal orthogonal subcategories

We introduce the concept of maximal (n−1)-orthogonal subcategories over Artin algebras and orders, and develop (n+1)-dimensional Auslander-Reiten theory on them. We give the n-Auslander-Reiten translation and the n-Auslander-Reiten duality, then show the existence of n-almost split sequences and n-fundamental sequences. We give some examples.     

There are no de bruijn sequences of span n with complexity 2n − 1 + n + 1

If s = (s₀, s₁,…, s_2ⁿ?1) is a binary de Bruijn sequence of span n, then it has been shown that the least length of a linear recursion that generates s, called the complexity of s and denoted by c(s), is bounded for n ? 3 by 2^{n ? 1} + n ? c(s) ? 2ⁿ ?1. A numerical study of the allowable values of c(s) for 3 ? n ? 6 found that all values in this range occurred except for 2^n?1 + n + 1. It is proven in this note that there are no de Bruijn sequences of complexity 2^n?1 + n + 1 for all n ? 3.     

The dynatomic periodic curves for polynomial z→z~d+c are smooth and irreducible

We prove here the smoothness and the irreducibility of the periodic dynatomic curves(c,z)∈C2such that z is n-periodic for zd+c,where d 2.We use the method provided by Buff and Lei where they proved the conclusion for d=2.The proof for smoothness is based on elementary calculations on the pushforwards of specific quadratic differentials,following Thurston and Epstein,while the proof for irreducibility is a simplified version of Lau-Schleicher’s proof by using elementary arithmetic properties of kneading sequence instead of internal addresses.     

Davenport constant for finite abelian groups

For a finite abelian group G, we investigate the length of a sequence of elements of G that is guaranteed to have a subsequence with product identity of G. In particular, we obtain a bound on the length which takes into account the repetitions of elements of the sequence, the rank and the invariant factors of G. Consequently, we see that there are plenty of such sequences whose length could be much shorter than the best known upper bound for the Davenport constant of G, which is the least integer s such that any sequence of length s in G necessarily contains a subsequence with product identity. We also show that the Davenport constant for the multiplicative group of reduced residue classes modulo n is comparatively large with respect to the order of the group, which is φ(n),when n is in certain thin subsets of positive integers. This is done by studying the Carmichael’s lambda function, defined as the maximal multiplicative order of any reduced residue modulo n, along these subsets.     

Graphs of difference operators for p-ary sequences

For a given prime p and positive integer n, we consider the graph G _n of the difference operator acting on p-ary sequences of length n. We suggest new proofs of some results of V.I. Arnold on the graph G _n and the complexity of sequences and obtain new results for the length of a maximal cycle in the general case of p-ary sequences. We also provide estimates for the number of complicated sequences.      

Enumeration of up-down sequences

Generalizing the notion of up-down permutations, the author considers sequences σ = (a₁, a₂, , α_N) of length N = s₂ + s₂ ++ s_n, where α_i ∈ {1, 2,n } and the element j occurs exactly s_j times. The repeated elements of a are labeled i, i′, i″, and it is assumed that they occur in a m natural order. Generating functions for the number of up-down sequences are constructed. Making use of the generating functions, explicit formulas for the number of up-down sequences are obtained.     

Iterations of linear maps over finite fields

We study the dynamics of the evolution of Ducci sequences and the Martin-Odlyzko-Wolfram cellular automaton by iterating their respective linear maps on . After a review of an algebraic characterization of cycle lengths, we deduce the relationship between the maximal cycle lengths of these two maps from a simple connection between them. For n odd, we establish a conjugacy relationship that provides a more direct identification of their dynamics. We give an alternate, geometric proof of the maximal cycle length relationship, based on this conjugacy and a symmetry property. We show that the cyclic dynamics of both maps in dimension 2n can be deduced from their periodic behavior in dimension n. This link is generalized to a larger class of maps. With restrictions shared by both maps, we obtain a formula for the number of vectors in dimension 2n belonging to a cycle of length q that expresses this number in terms of the analogous values in dimension n.     

Pattern Frequency Sequences and Internal Zeros

Let q be a pattern and let S_n, q(c) be the number of n-permutations having exactly c copies of q. We investigate when the sequence (S_n, q(c))_c ≥ 0 has internal zeros. If q is a monotone pattern it turns out that, except for q = 12 or 21, the nontrivial sequences (those where n is at least the length of q) always have internal zeros. For the pattern q = 1(l + 1)l…2 there are infinitely many sequences which contain internal zeros and when l = 2 there are also infinitely many which do not. In the latter case, the only possible places for internal zeros are the next-to-last or the second-to-last positions. Note that by symmetry this completely determines the existence of internal zeros for all patterns of length at most 3.     

Departure from normality of increasing-dimension martingales

In this paper, we consider sequences of vector martingale differences of increasing dimension. We show that the Kantorovich distance from the distribution of the k(n)-dimensional average of n martingale differences to the corresponding Gaussian distribution satisfies certain inequalities. As a consequence, if the growth of k(n) is not too fast, then the Kantorovich distance converges to zero. Two applications of this result are presented. The first is a precise proof of the asymptotic distribution of the multivariate portmanteau statistic applied to the residuals of an autoregressive model and the second is a proof of the asymptotic normality of the estimates of a finite autoregressive model when the process is an AR(∞) and the order of the model grows with the length of the series.     

Solving enumeration problems for serial sequences with a constant difference in adjacent series heights

In this paper, the sets of n-valued serial sequences are considered. The structure of such series is defined by constraints on the number of series, the length of series, and the height of series. The problem of recalculation, numeration, and generation is solved for the sets of ascending, descending, and one-transitive sequences with constant differences in the adjacent series heights.     

The number of indecomposable codes

A CUPS class of codes is a class that is closed under external direct sums, projections onto components of external direct sums, and formation of equivalent codes. In this paper, formulas are developed to compute the number of indecomposable codes of length n and the number of indecomposable (n, k) codes (both with full support) in a CUPS class $\text{C}$ in terms of the total number of length n and (n, k) codes, respectively, in $\text{C}$. Applications include complete computations of the total number of indecomposable length n codes, the number of indecomposable (n, k) codes, the number of indecomposable (n, k) codes of minimum distance 3 or more, the number of indecomposable length n self-dual codes, and the number of indecomposable length n self-dual codes with minimum distance 4 or more.     

The convex hull of degree sequences of signed graphs

As shown in [D. Hoffman, H. Jordon, Signed graph factors and degree sequences, J. Graph Theory 52 (2006) 27-36], the degree sequences of signed graphs can be characterized by a system of linear inequalities. The set of all n-tuples satisfying this system of linear inequalities is a polytope P_n. In this paper, we show that P_n is the convex hull of the set of degree sequences of signed graphs of order n. We also determine many properties of P_n, including a characterization of its vertices. The convex hull of imbalance sequences of digraphs is also investigated using the characterization given in [D. Mubayi, T.G. Will, D.B. West, Realizing degree imbalances of directed graphs, Discrete Math. 239 (2001) 147-153].