Enumerating pairs of permutations with the same up-down form

For each sequence q = {q_i} = ± 1, i = 1, …, n−1 let N_q = the number of permutations σ of 1, 2, …, n with up-down sequence sgn(σ_i+1 − σ_i) = q_i, i = 1,…, n−1. Clearly Σ_q (N_q/n!) =1 but what is the probability p_n = Σ_q (N_q/n!)² that two random permutations have the same up-down sequence? We show that p_n = (Kⁿ⁻¹1,1) where 1 = 1(x, y) ≡ 1 and Kⁿ⁻¹ is the iterated integral operator with Kφ(x, y) = ∫₀¹∫₀¹ K(x, y; x′, y′)φ(x′, y′) dx′ dy′ on L²[0, 1] × [0, 1] where K(x, y; x′, y′) is 1 if (x− x′)(y − y′) > 0 otherwise, and (f, g) = ∫₀¹∫₀¹fg. The eigenexpression of K yeilds p_n ∼ cαⁿ as n → ∞, where c ≈ 1.6, α ≈ 0.55.We also give a recursion formula for a polynomial whose coefficients are the frequencies of all the possible forms.     

Linear transformations on matrices: the invariance of generalized permutation matrices—III

Let F be a field, F1 be its multiplicative group, and $\text{H}$ = {H:H is a subgroup of F1 and there do not exist a, b?F1 such that Ha+b?H}. Let D_n be the dihedral group of degree n, H be a nontrivial group in $\text{H}$, and τ_n(H) = {α = (α₁, α₂,…, α_n):α_i?H}. For σ?D_n and α?τ_n(H), let P(σ, α) be the matrix whose (i,j) entry is α_iδ_iσ(j) (i.e., a generalized permutation matrix), and

$\text{P(D}{}_{\mathrm{n}}\text{, H) = {P(σ, α):σ?D}{}_{\mathrm{n}}\text{, α?τ}{}_{\mathrm{n}}\text{(H)}}$

. Let M_n(F) be the vector space of all n×n matrices over F and $\text{T}$P(D_n, H) = {T:T is a linear transformation on M_n (F) to itself and T(P(D_n, H)) = P(D_n, H)}. In this paper we classify all T in $\text{T}$P(D_n, H) and determine the structure of the group $\text{T}$P(D_n, H) (Theorems 1 to 4). An expository version of the main results is given in Sec. 1, and an example is given at the end of the paper.     

On the dimension of the space of ℝ-places of certain rational function fields

We prove that for every n ∈ ? the space M(K(x ₁, …, x _n ) of ?-places of the field K(x ₁, …, x _n ) of rational functions of n variables with coefficients in a totally Archimedean field K has the topological covering dimension dimM(K(x ₁, …, x _n )) ≤ n. For n = 2 the space M(K(x ₁, x ₂)) has covering and integral dimensions dimM(K(x ₁, x ₂)) = dim_? M(K(x ₁, x ₂)) = 2 and the cohomological dimension dim _G M(K(x ₁, x ₂)) = 1 for any Abelian 2-divisible coefficient group G.     

Torsion points of elliptic curves over large algebraic extensions of finitely generated fields

The following Theorem is proved:Let K be a finitely generated field over its prime field. Then, for almost all e-tuples (σ)=(σ ₁, …,σ _e)of elements of the abstract Galois group G(K)of K we have:

1. If e=1,then E _tor(K(σ))is infinite. Morover, there exist infinitely many primes l such that E(K(σ))contains points of order l.
2. If e≧2,then E _tor(K(σ))is finite.
3. If e≧1,then for every prime l, the group E(K(σ))contains only finitely many points of an l-power order.

HereK(σ) is the fixed field in the algebraic closureK ofK, ofσ ₁, …,σ _e, and “almost all” is meant in the sense of the Haar measure ofG(K).     

More coverings by rook domains

The set V_kⁿ of all n-tuples (x₁, x₂,…, x_n) with x_i?, $\text{Z}$_k is considered. The problem treated in this paper is determining σ(n, k), the minimum size of a set W ? V_kⁿ such that for each x in V_kⁿ, there is an element in W that differs from x in at most one coordinate. By using a new constructive method, it is shown that σ(n, p) ? (p ? t + 1)p^n?r, where p is a prime and $\text{n = 1 +}\text{t(p}{}^{\mathrm{r?1}}\text{? 1)}\text{(p ? 1)}$ for some integers t and r. The same method also gives σ(7, 3) ? 216. Another construction gives the inequality σ(n, kt) ? σ(n, k)t^n?1 which implies that σ(q + 1, qt) = q^q?1t^q when q is a prime power. By proving another inequality σ(np + 1, p) ? σ(n, p)p^n(p?1), σ(10, 3) ? 5 · 3⁶ and σ(16, 5) ? 13 · 5¹² are obtained.     

Permutations and successions

Let π = (π(1), π(2),…, π(n)) be a permutation on {1, 2, …, n}. A succession (respectively, ¹-succession) in π is any pair π(i), π(i + 1), where π(i + 1) = π(i) + 1 (respectively, π(i + 1) ≡ π(i) + 1 (mod n)), i = 1, 2, …, n ? 1. Let R(n, k) (respectively, $\text{R}{}^1\text{(n, k)}$) be the number of permutations with k successions (respectively, ¹-successions). In this note we determine R(n, k) and $\text{R}{}^1\text{(n, k)}$. In addition, these notions are generalized to the case of circular permutations, where analogous results are developed.     

A proof of the q,t-Catalan positivity conjecture

We present here a proof that a certain rational function C_n(q,t) which has come to be known as the “q,t-Catalan” is in fact a polynomial with positive integer coefficients. This has been an open problem since 1994. The precise form of the conjecture is given in Garsia and Haiman (J. Algebraic Combin. 5(3) (1996) 191), where it is further conjectured that C_n(q,t) is the Hilbert series of the diagonal harmonic alternants in the variables (x₁,x₂,…,x_n;y₁,y₂,…,y_n). Since C_n(q,t) evaluates to the Catalan number at t=q=1, it has also been an open problem to find a pair of statistics a(π),b(π) on Dyck paths π in the n×n square yielding C_n(q,t)=∑_πt^a(π)q^b(π). Our proof is based on a recursion for C_n(q,t) suggested by a pair of statistics a(π),b(π) recently proposed by Haglund. Thus, one of the byproducts of our developments is a proof of the validity of Haglund's conjecture. It should also be noted that our arguments rely and expand on the plethystic machinery developed in Bergeron et al. (Methods and Applications of Analysis, Vol. VII(3), 1999, p. 363).     

Some results on Hu's conjecture concerning binary trees

Given n weights, w₁, w₂,…, w_n, such that 0?w₁?w₂???w₁, we examine a property of permutation π¹, where π¹=(w₁, w_n, w₂, w_n?1,…), concerning alphabetical binary trees.For each permutation π of these n weights, there is an optimal alphabetical binary tree corresponding to π, we denote it's cost by V(π). There is also an optimal almost uniform alphabetical binary tree, corresponding to π, we denote it's cost by V_u(π).This paper asserts that V_u(π¹)?V_u(π)?V(π) for all π. This is a preliminary result concerning the conjecture of T.C. Hu. Hu's conjecture is V(π¹)?V(π) for all π.     

On theT-ideal generated by a standard identity

We determine the structure of the ideal of identities of degreen +1 in theT-ideals T_o(s_n(x₁,…,x_n)) and T_o(u_n(x₁,…,x_n)), wheres _n is the standard identity and u_n the unitary identity of degreen.     

Lower bounds on covering codes via partition matrices

Let Kq(n,R) denote the minimal cardinality of a q-ary code of length n and covering radius R. Let σq(n,s;r) denote the minimal cardinality of a q-ary code of length n, which is s-surjective with radius r. In order to lower-bound Kq(n,n−2) and σq(n,s;s−2) we introduce partition matrices and their transversals. Our approach leads to a short new proof of a classical bound of Rodemich on Kq(n,n−2) and to the new bound Kq(n,n−2)?3q−2n+2, improving the first iff 5?n<q?2n−4. We determine Kq(q,q−2)=q−2+σ₂(q,2;0) if q?10. Moreover, we obtain the new powerful recursive bound Kq+1(n+1,R+1)?min{2(q+1),Kq(n,R)+1}.     

The interval number of a complete multipartite graph

The interval number of a graph G, denoted i(G), is the least positive integer t for which G is the intersection graph of a family of sets each of which is the union of at most t closed intervals of the real line $\text{R}$. Trotter and Harary showed that the interval number of the complete bipartite graph K(m,n) is $\text{?}\text{(mn + 1)}\text{(m + n)}\text{?}$. Matthews showed that the interval number of the complete multipartite graph K(n₁,n₂,…,n_p) was the same as the interval number of K(n₁,n₂) when n₁ = n₂ = ? = n_p. Trotter and Hopkins showed that i(K(n₁,n₂,…,n_p)) ≤ 1 + i(K(n₁,n₂)) whenever p ≥ 2 and n₁≥n₂≥ ? ≥n_p. West showed that for each n ≥ 3, there exists a constant c_n so that if p ≥ c_n,n₁ = n²?n ?1, and n₂ = n₃ = ? n_p = n, then i(K(n₁,n₂,…,n_p) = 1 + i(K(n₁, n₂)). In view of these results, it is natural to consider the problem of determining those pairs (n₁,n₂) with n₁ ≥ n₂ so that i(K(n₂,…,n_p)) = i(K(n₁,n₂)) whenever p ≥ 2 and n₂ ≥ n₃ ≥ ? ≥ n_p. In this paper, we present constructions utilizing Eulerian circuits in directed graphs to show that the only exceptional pairs are (n² ? n ? 1, n) for n ≥ 3 and (7,5).     

On convergence of LAD estimates in autoregression with infinite variance

The least absolute deviation estimates L(N), from N data points, of the autoregressive constants a = (a₁, …, a_q)′ for a stationary autoregressive model, are shown to have the property that N^σ(L(N) ? a) converge to zero in probability, for $\text{σ <}\text{1}\text{α}$, where the disturbances are i.i.d., attracted to a stable law of index α, 1 ≤ α < 2, and satisfy some other conditions.     

Alternating sequences

Let a=(α₁, α₂, α₃, …) be a sequence of positive integers. The sequence (c₁, c₂, …, c₃) is a-alternating if 1 ? c₁ < c₂ < … < c_k ? n and in additionthe first α₁ elements have the same parity, the next α₂ elements have opposite parity, the next α₃ elements have the parity of the first group, and so on. The final group of elements of like parity is permitted to have fewer elements than the required number. Let $\text{?(a; n, k)}$ denote the number of a-alternating sequences of length k. An explicit formula for $\text{? (a;n, k)}$ is obtained.     

The embedding of (0, α)-geometries in PG(n, q): part II

In Part I we obtained results about the embedding of (0, α)-geometries in PG(3, q). Here we determine all (0, α)-geometries with q+1 points on a line, which are embedded in PG(n, q), n>3 and q>2. As a particular case all semi partial geometries with parameters s=q,t,α(>1),μ, which are embeddable in PG(n, q), q≠2, are obtained. We also prove some theorems about the embedding of (0, 2)-geometries in PG(n, 2): we show that without loss of generality we may restrict ourselves to reduced (0, 2)-geometries, we determine all (0, 2)-geometries in PG(4, 2), and we describe an unusual embedding of U_2,3(9) in PG(5, 2).     

An application of L-functions of imaginary quadratic fields

Let F₁(x, y),…, F_2h+1(x, y) be the representatives of equivalent classes of positive definite binary quadratic forms of discriminant ?q (q is a prime such that q ≡ 3 mod 4) with integer coefficients, then the number of integer solutions of F_i(x, y) = n (i = 1,…, 2h + 1) can be calculated for each natural number n using L-functions of imaginary quadratic field $\text{Q}$((?q)^1/2).     

The Rotation Number Approach to the Periodic Fuc caron ik Spectrum

In this paper, we study the Fu?ik spectrum of the problem: (^*) ?+(λ₊+q₊(t))x₊+(λ₋+q₋(t))x₋=0 with the 2π-periodic boundary condition, where q_±(t) are 2π-periodic. After introducing a rotation number function ρ(λ₊, λ₋) for (^*), we prove using the Hamiltonian structure and the positive homogeneity of (^*) that for any positive integer n, the two boundary curves of the domain ρ⁻¹(n/2) in the (λ₊, λ₋)-plane are Fu?ik curves of (^*). The result obtained in this paper shows that such a spectrum problem is much like that of the higher dimensional Fu?ik spectrum with the Dirichlet condition. In particular, it remains open if the Fu?ik spectrum of (^*) is composed of only these curves.     

Some consequences of the general Riemann hypothesis in the comparative theory of primes

Several effective results are proved about oscillatory properties of π(x, q, l₁) − π(x, q, l₂) and related functions assuming the General Riemann Hypothesis and the absence of real zeros of L-functions.     

Existence of stable equilibrium point for dynamical systems of Volterra type

This paper presents sufficient conditions for the existence of a nonnegative and stable equilibrium point of a dynamical system of Volterra type, (1) $\text{(}\text{d}\text{dt}\text{) x}{}_{\mathrm{i}}\text{(t) = ?x}{}_{\mathrm{i}}\text{(t)[f}{}_{\mathrm{i}}\text{(x}{}_1\text{(t),…, x}{}_{\mathrm{n}}\text{(t)) ? q}{}_{\mathrm{i}}\text{], i = 1,…, n}$, for every q = (q₁,…, q_n)^T?Rⁿ. Results of a nonlinear complementarity problem are applied to obtain the conditions. System (1) has a nonnegative and stable equilibrium point if (i) f(x) = (f₁(x),…,f_n(x))^T is a continuous and differentiable M-function and it satisfies a certain surjectivity property, or (ii), f(x) is continuous and strongly monotone on R₊₀ⁿ.     

Asymptotics of the complexity of systems of integer linear forms for additive computations

The computational complexity of integer linear forms is studied. By l ₂(A) we denote the minimal number of the additions and subtractions required for computing the system of p linear forms in q variables x ₁, x ₂, …, x _q that are defined by an integer matrix A of size p × q (repeated use of the results of intermediate computation is permitted). We show that l ₂(A) ? log D(A), where D(A) is the maximum of the absolute values of the minors of A over all minors from order 1 to order min (p, q) (Theorem 1). Moreover, for each sequence of matrices A(n) of size p(n) × q(n) satisfying the condition p + q = o ((log log D(A))^1/2) as n → ∞ the bound l ₂(A) ? log D(A) + o(log D(A)) is valid (Theorem 2). Hence, for all fixed (and even weakly increasing) sizes of matrices that determine a system of integer linear forms, the upper bound on the computational complexity of this system is asymptotically equal to the lower bound.     

Generalizations of weakly peripherally multiplicative maps between uniform algebras

Let A and B be uniform algebras on first-countable, compact Hausdorff spaces X and Y, respectively. For f∈A, the peripheral spectrum of f, denoted by σπ(f)={λ∈σ(f):|λ|=‖f‖}, is the set of spectral values of maximum modulus. A map T:A→B is weakly peripherally multiplicative if σπ(T(f)T(g))∩σπ(fg)≠∅ for all f,g∈A. We show that if T is a surjective, weakly peripherally multiplicative map, then T is a weighted composition operator, extending earlier results. Furthermore, if T₁,T₂:A→B are surjective mappings that satisfy σπ(T₁(f)T₂(g))∩σπ(fg)≠∅ for all f,g∈A, then T₁(f)T₂(1)=T₁(1)T₂(f) for all f∈A, and the map f?T₁(f)T₂(1) is an isometric algebra isomorphism.