Transposition generation of alternating permutations

A permutation _{1 2}... _n is alternating if ₁< ₂> ₃< ₄.... Alternating permutations are counted by the Euler numbers. Here we show that alternating permutations can be listed so that successive permutations differ by a transposition, ifn is odd. Extensions and open problems are mentioned.Research supported by the Natural Sciences and Engineering Research Council of Canada under grant A3379.     

On Tabor's problem concerning a certain quasi-ordering of iterative roots of functions

Summary Using the Isaacs-Zimmermann's theory of iterative roots of functions, we prove a theorem concerning the problemP 250 posed by J. Tabor:Letf: E E be a given mapping. Denote byF the set of all iterative roots off. InF we define the following relation: if and only if is an iterative root of. The relation is obviously reflexive and transitive. The question is: Is it also antisymmetric? If we consider iterative roots of a monotonic function the answer is yes. But in general the question is open.Here we prove that there exists a three-element decomposition { _i ;i = 1, 2, 3} of the setE ^E with blocks _i of the same cardinality 2^cardE such that the functions from ₁ do not possess any proper iterative root, the quasi-ordering is not antisymmetric onF(f) for anyf ₂, and is an ordering onF(f) for anyf ₃. Iff is a strictly increasing continuous self-bijection ofE, then the relation is an ordering onF(f) ifff is different from the identity mapping of the setE.     

On the congruence problem in infinite dimensional sesquilinear spaces

If two subspaces V and V of a sesquilinear space E are congruent (i.e., there is an isometry : E E with (V)=V) then their corresponding quadratic lattices V(V, E) and V(V, E) are isomorphic. It is shown that the converse holds for important types of sesquilinear spaces E, provided that dim(E) ₃. However, the converse generally fails if dim(E) ₃.     

On Vector Valued Measure Spaces of Bounded Φ-variation containing copies of ℓ∞

Given a Young function , we study the existence of copies of c ₀ and in cabv (,X) and in cabsv (,X), the countably additive, -continuous, and X-valued measure spaces of bounded -variation and bounded -semivariation, respectively.     

The core of a chain complete poset with no one-way infinite fence and no tower

Like dismantling for finite posets, a perfect sequence = P : of a chain complete posetP represents a canonical procedure to produce a coreP . It has been proved that if the posetP contains no infinite antichain then this coreP is a retract ofP andP has the fixed point property iffP has this property. In this paper the condition of having no infinite antichain is replaced by a weaker one. We show that the same conclusion holds under the assumption thatP does not contain a one-way infinite fence or a tower.Supported by a grant from The National Natural Science Foundation of China.     

Random orders

Letk andn be positive integers and fix a setS of cardinalityn; letP _k (n) be the (partial) order onS given by the intersection ofk randomly and independently chosen linear orders onS. We begin study of the basic parameters ofP _k (n) (e.g., height, width, number of extremal elements) for fixedk and largen. Our object is to illustrate some techniques for dealing with these random orders and to lay the groundwork for future research, hoping that they will be found to have useful properties not obtainable by known constructions.Supported by NSF grant MCS 84-02054.     

A Favard theorem for orthogonal rational functions on the unit circle

We consider forn=0, 1,... the nested spaces _n of rational functions of degreen at most with given poles . Given a finite measure supported on the unit circle, we associate with it a nested orthogonal basis of rational functions ₀,..., _n for _n ,n=0, 1,.... These _n satisfy a recurrence relation that generalizes the recurrence for Szeg polynomials.In this paper we shall prove a Favard type theorem which says that if one has a sequence of rational functions _{n n} which are generated by such a recurrence, then there will be a measure supported on the unit circle to which they are orthogonal. We shall give a sufficient condition for the uniqueness of this measure.     

Cross-monotone subsequences

Two finite real sequences (a ₁,...,a _k ) and (b ₁,...,b _k ) are cross-monotone if each is nondecreasing anda _i+1–a _i b _i+1–b _i for alli. A sequence (₁,..., _n ) of nondecreasing reals is in class CM(k) if it has disjointk-term subsequences that are cross-monotone. The paper shows thatf(k), the smallestn such that every nondecreasing (₁,..., _n ) is in CM(k), is bounded between aboutk ²/4 andk ₂/2. It also shows thatg(k), the smallestn for which all (₁,..., _n ) are in CM(k)and eithera _k b ₁ orb _k a ₁, equalsk(k–1)+2, and thath(k), the smallestn for which all (₁,..., _n ) are in CM(_k)and eithera ₁b ₁...a _k b _k orb ₁a ₁...b _k a _k , equals 2(k–1)²+2.The results forf andg rely on new theorems for regular patterns in (0, 1)-matrices that are of interest in their own right. An example is: Every upper-triangulark ²×k ² (0, 1)-matrix has eitherk 1's in consecutive columns, each below its predecessor, ork 0's in consecutive rows, each to the right of its predecessor, and the same conclusion is false whenk ² is replaced byk ²–1.     

Angle orders,regular n-gon orders and the crossing number

A finite poset P(X,<) on a set X={ x ₁,...,x _m} is an angle order (regular n-gon order) if the elements of P(X,<) can be mapped into a family of angular regions on the plane (a family of regular polygons with n sides and having parallel sides) such that x _ij if and only if the angular region (regular n-gon) for x _i is contained in the region (regular n-gon) for x _j. In this paper we prove that there are partial orders of dimension 6 with 64 elements which are not angle orders. The smallest partial order previously known not to be an angle order has 198 elements and has dimension 7. We also prove that partial orders of dimension 3 are representable using equilateral triangles with the same orientation. This results does not generalizes to higher dimensions. We will prove that there is a partial order of dimension 4 with 14 elements which is not a regular n-gon order regardless of the value of n. Finally, we prove that partial orders of dimension 3 are regular n-gon orders for n3.This research was supported by the Natural Sciences and Engineering Research Council of Canada, grant numbers A0977 and A2415.     

On Right Symmetric and Novikov Nil-Algebras of Bounded Index

Let be a field of characteristic zero. It is proved that a right symmetric nil-algebra of index n over is right nilpotent, and a Novikov nil-algebra of index n over is nilpotent.     

A class of nonseparable dynamic programming problems

A solution procedure is proposed for a class of deterministic sequential decision problems whose objective functions are of the form f _n(x _n)+(g _n(x _n)) where is differentiable and either concave or convex. The procedure calls for the collaboration between dynamic programming and c-programming, and is demonstrated in our treatment of a minimum variance type problem.     

Formal Flows on the Non-Archimedean Open Unit Disk

This paper deals with group actions of one-dimensional formal groups defined over the ring of integers in a finite extension of the p-adic field, where the space acted upon is the maximal ideal in the ring of integers of an algebraic closure of the p-adic field. Given a formal group F as above, a formal flow is a series (t,x) satisfying the conditions (0,x)=x and (F(s,t),x)=(s,(t,x)). With this definition, any formal group will act on the disk by left translation, but this paper constructs flows with any specified divisor of fixed points, where a point of the open unit disk is a fixed point of order n if (x–) ⁿ |((t,x)–x). Furthermore, if is an analytic automorphism of the open unit disk with only finitely many periodic points, then there is a flow , an element of the maximal ideal of the ring of constants, and an integer m such that the m-fold iteration of (x) is equal to (,x). All the formal flows constructed here are actions of the additive formal group on the unit disk. Indeed, if the divisor of fixed points of a formal flow is of degree at least two, then the formal group involved must become isomorphic to the additive group when the base is extended to the residue field of the constant ring.     

Extremal problems for linear orders on [n] p

Let be a product order on [n] ^p i.e. for A, B [n] ^p , 1a ₁<a ₂<...<a _p º-n and 1<-b ₁<b ₂<...<b _p <-n we have AB iff a _i<-b _i for all i=1, 2,..., p. For a linear extension < of (ordering [n] ^p as ) let F _< ^[n],p (m) count the number of A _i 's, i<-m such that 1A _i. Clearly, for every m and <, where <l denotes the lexicographic order on [n] ^p . In this note we prove that the colexicographical order, <c, provides a corresponding lower bound i.e. that holds for any linear extension < of .This project together with [2] was initiated by the first author and continued in colaboration with the second author. After the death of the first author the work was continued and finalized by the second and the third author.Research supported by NSF grant DMS 9011850.     

Partial Orders on Transformation Semigroups

In 1986, Kowol and Mitsch studied properties of the so-called natural partial order on T(X), the total transformation semigroup defined on a set X. In particular, they determined when two total transformations are related under this order, and they described the minimal and maximal elements of (T(X), ). In this paper, we extend that work to the semigroup P(X) of all partial transformations of X, compare with another natural partial order on P(X), characterise the meet and join of these two orders, and determine the minimal and maximal elements of P(X) with respect to each order.This author gratefully acknowledges the generous support of Centro de Matematica, Universidade do Minho, Portugal during his visit in May–June 2001.Received May 27, 2002; in revised form November 27, 2002 Published online May 16, 2003     

On generalized gamma functions related to the Laurent coefficients of the Riemann zeta function

Summary We study a class of generalized gamma functions _k (z) which relate to the generalized Euler constants _k (basically the Laurent coefficients of(s)) as (z) does to the Euler constant. A new series expansion for _k is derived, and the constant term in the asymptotic expansion for log _k (z) is studied in detail. These and related constants are numerically computed for 1 k 15.     

Two combinatorial problems on posets

Bialostocki proposed the following problem: Let nk2 be integers such that k|n. Let p(n, k) denote the least positive integer having the property that for every poset P, |P|p(n, k) and every Z _k -coloring f: P Z _k there exists either a chain or an antichain A, |A|=n and _aA f(a) 0 (modk). Estimate p(n, k). We prove that there exists a constant c(k), depends only on k, such that (n+k–2)²–c(k) p(n, k) (n+k–2)²+1. Another problem considered here is a 2-dimensional form of the monotone sequence theorem of Erdös and Szekeres. We prove that there exists a least positive integer f(n) such that every integral square matrix A of order f(n) contains a square submatrix B of order n, with all rows monotone sequences in the same direction and all columns monotone sequences in the same direction (direction means increasing or decreasing).     

Über die Minimalflächen des isotropen Raumes,welche zugleich Affinminimalflächen sind

One determines all the minimal surfaces of the isotropic space, which simultaneously are affinminimal surfaces. A characteristic property of those surfaces is that the isotropic spherical imagines of the asymptotic lines of form two orthogonal pencils of circles. There are three types of such surfaces : first the well known right helicoid _I , second an interesting transcendental surface _II , and third the isotropic analogy _III of the minimal surface ofEnneper. The surfaces permit cinematic generations. Especially _II and _III can be generated byClifford screws in a certain indefinite quasielliptic space.In the isotropic space conjugate to the surfaces are isotropic minimal surfaces ^* with plane lines of curvature. There are also three types of such surfaces: _I ^* is a logarithmic surface of revolution, _II ^* is an interesting transcendental surface, and _III ^* is again the isotropic minimal surface ofEnnerper.     

A characterization ofL n(K) as a permutation group

In 1972 M. O'Nan proved thatL _n (q),h 3; can be characterized as a doubly-transitive groupG on a finite set , whereG _a has an Abelian normal subgroup acting not semi-regularly on -a. In the Main Theorem we show that a similar statement holds if is infinite. Our result implies O'Nan's theorem.This paper is part of the author's Ph.D. thesis written under supervision of Prof. F. G. Timmesfeld.     

Partially ordered permutation groups

In this note we discuss permutation groups (G, ) in which the set admits aG-invariant order. By aG-invariant partial order (G-partial order) we mean a partial order < of such that < implies g<g, for all and in andg inG. If the set admits aG-partial order which is a total order, then (G, ) is an O-permutation group (orderable permutation group).The main concern of this paper is the development of a foundation for partially ordered permutation groups analogous to the existing one for partially ordered groups, as found in Fuchs [2].     

Convergence des solutions formelles de certaines équations fonctionnelles

Résumé Soitq un nombre algébrique de module 1, qui ne soit pas une racine de l'unité, etP [X, Y ₀,Y ₁] un polynôme non nul. Dans cet article, nous montrons que toute solution de l'équation fonctionnelleP(z, (z), (qz))=0, qui est une série formelle (z) dansQ[[z]], a un rayon de convergence non nul.

---

Summary Letq Q be an algebraic number of modulus one that is not a root of unity. LetP Q[X, Y ₀,Y ₁] be a non zero polynomial. In this paper, we show that every formal power series,(z) Q[[z]], solution of the functional equationP(z), (z), (qz)) = 0 has a non zero radius of convergence.