Restricted even permutations and Chebyshev polynomials

We study generating functions for the number of even (odd) permutations on n letters avoiding 132 and an arbitrary permutation τ on k letters, or containing τ exactly once. In several interesting cases the generating function depends only on k and is expressed via Chebyshev polynomials of the second kind.     

Restricted 132-Alternating Permutations and Chebyshev Polynomials

A permutation is said to be alternating if it starts with rise and then descents and rises come in turn. In this paper we study the generating function for the number of alternating permutations on n letters that avoid or contain exactly once 132 and also avoid or contain exactly once an arbitrary pattern on k letters. In several interesting cases the generating function depends only on k and is expressed via Chebyshev polynomials of the second kind.AMS Subject Classification: 05A05, 05A15, 30B70, 42C05.     

On a nonlinear stochastic integral equation with application to control systems

The aim of the present paper is to study a nonlinear stochastic integral equation of the form

(2, 3, k)-generated groups of large rank

For any fixed k 3 7k \geq 7 there exist integers n_k and a_k such that if the ring R is generated by a set of m elements t₁,...,t_m, where 2t₁-t₁²2t_1-t_1^2 is a unit of finite multiplicative order, and n 3 n_k+ma_kn \geq n_k+ma_k, then the group E_n(R) generated by elementary transvections is an epimorphic image of the triangle group D(2,3,k).\Delta (2,3,k).     

Funktionen, deren Maxima eine asymptotisch konstante Folge bilden

Es sei M₁ die Klasse der reellwertigen Funktionen f derart, daß lim_{tk? ￥} |f(t_k)| = c\lim \limits _{t_k\to \infty } |f(t_k)| = c gilt, wobei |f(t_k)||f(t_k)| die lokalen Maxima von | f | und c = c (f) eine positive Konstante ist. Diese Klasse tritt häufig im Zusammenhang mit Differentialgleichungen auf und ist kürzlich Gegenstand von mehreren Arbeiten geworden. Oft gelingt es, nur mf ? M₁mf \in M_1 mit einer passenden Funktion m ~ 1m\sim 1 zu zeigen, und es erhebt sich die Frage, ob daraus f ? M₁f \in M_1 folgt. Diese Frage wird hier für eine Unterklasse M ì M₁M \subset M_1 untersucht. Unsere Ergebnisse füllen eine Lücke in früheren Arbeiten und sind unserer Meinung nach auch für sich selbst von Interesse.     

A wavelike functional equation of Pexider type

Summary. Let (G, +) and (H, +) be abelian groups such that the equation 2u = v 2u = v is solvable in both G and H. It is shown that if f₁, f₂, f₃, f₄, : G ×G ? H f_1, f_2, f_3, f_4, : G \times G \longrightarrow H satisfy the functional equation f₁(x + t, y + s) + f₂(x - t, y - s) = f₃(x + s, y - t) + f₄(x - s, y + t) for all x, y, s, t ? G x, y, s, t \in G , then f₁, f₂, f₃, and f₄ are given by f₁ = w + h, f₂ = w - h, f₃ = w + k, f₄ = w - k where w : G ×G ? H w : G \times G \longrightarrow H is an arbitrary solution of f (x + t, y + s) + f (x - t, y - s) = f (x + s, y - t) + f (x - s, y + t) for all x, y, s, t ? G x, y, s, t \in G , and h, k : G ×G ? H h, k : G \times G \longrightarrow H are arbitrary solutions of D_y,t³g(x,y) = 0 \Delta_{y,t}^{3}g(x,y) = 0 and D_x,t³g(x,y) = 0 \Delta_{x,t}^{3}g(x,y) = 0 for all x, y, s, t ? G x, y, s, t \in G .     

On the derivatives of X-ray functions

We show that for every n \geqq 4, 0 \leqq k \leqq n - 3, p ? (0, 3] n \geqq 4, 0 \leqq k \leqq n - 3, p \in (0, 3] and every origin-symmetric convex body K in \mathbbRⁿ \mathbb{R}^n , the function ||x ||^-k₂ ||x ||^-n+k+p_K \parallel x \parallel^{-k}_{2} \parallel x \parallel^{-n+k+p}_{K} represents a positive definite distribution on \mathbbRⁿ \mathbb{R}^n , where ||·||₂ \parallel \cdot \parallel_{2} is the Euclidean norm and ||·||_K \parallel \cdot \parallel_{K} is the Minkowski functional of K. We apply this fact to prove a result of Busemann-Petty type that the inequalities for the derivatives of order (n - 4) at zero of X-ray functions of two convex bodies imply the inequalities for the volume of average m-dimensional sections of these bodies for all 3 \leqq m \leqq n 3 \leqq m \leqq n . We also prove a sharp lower estimate for the maximal derivative of X-ray functions of the order (n - 4) at zero.     

How quadratic are the natural numbers?

Abstract. For natural numbers n we inspect all factorizations n = ab of n with a ￡ ba \le b in \Bbb N\Bbb N and denote by n=a_n b_nn=a_n b_n the most quadratic one, i.e. such that b_n - a_nb_n - a_n is minimal. Then the quotient k(n) : = a_n/b_n\kappa (n) := a_n/b_n is a measure for the quadraticity of n. The best general estimate for k(n)\kappa (n) is of course very poor: 1/n ￡ k(n) ￡ 11/n \le \kappa (n)\le 1. But a Theorem of Hall and Tenenbaum [1, p. 29], implies(logn)^-d-e ￡ k(n) ￡ (logn)^-d(\log n)^{-\delta -\varepsilon } \le \kappa (n) \le (\log n)^{-\delta } on average, with d = 1 - (1+log₂  2)/log2=0,08607 ?\delta = 1 - (1+\log _2 \,2)/\log 2=0,08607 \ldots and for every e > 0\varepsilon >0. Hence the natural numbers are fairly quadratic.¶k(n)\kappa (n) characterizes a specific optimal factorization of n. A quadraticity measure, which is more global with respect to the prime factorization of n, is k^*(n): = ?_{1 ￡ a ￡ b, ab=n} a/b\kappa ^*(n):= \textstyle\sum\limits \limits _{1\le a \le b, ab=n} a/b. We show k^*(n) ~ \frac 12\kappa ^*(n) \sim \frac {1}{2} on average, and k^*(n)=W(2^{\frac 12(1-e) log n/log ₂n})\kappa ^*(n)=\Omega (2^{\frac {1}{2}(1-\varepsilon ) {\log}\, n/{\log} _2n})for every e > 0\varepsilon>0.     

Embedding of non-commutative <Emphasis Type="Italic">L</Emphasis><Superscript><Emphasis Type="Italic">p</Emphasis></Superscript>-spaces: <Emphasis Type="Italic">p</Emphasis> < 1

If (N,t) ({\cal N},\tau) is a finite von Neumann algebra and if (M,n) ({\cal M},\nu) is an infinite von Neumann algebra, then L_p(M,n) L_{p}({\cal M},\nu) does not Banach embed in L_p(N,t) L_{p}({\cal N},\tau) for all p ? (0,1) p\in (0,1) . We also characterize subspaces of $ L_{p}({\cal N},\tau),\ 0< p <1 $ L_{p}({\cal N},\tau),\ 0< p <1 containing a copy of l_p.     

Efficient Testing of Large Graphs

Let P be a property of graphs. An e\epsilon -test for P is a randomized algorithm which, given the ability to make queries whether a desired pair of vertices of an input graph G with n vertices are adjacent or not, distinguishes, with high probability, between the case of G satisfying P and the case that it has to be modified by adding and removing more than en²\epsilon n^2 edges to make it satisfy P. The property P is called testable, if for every e\epsilon there exists an e\epsilon -test for P whose total number of queries is independent of the size of the input graph. Goldreich, Goldwasser and Ron [8] showed that certain individual graph properties, like k-colorability, admit an e\epsilon -test. In this paper we make a first step towards a complete logical characterization of all testable graph properties, and show that properties describable by a very general type of coloring problem are testable. We use this theorem to prove that first order graph properties not containing a quantifier alternation of type ``"$\forall \exists ' are always testable, while we show that some properties containing this alternation are not.     

A linear functional equation with a singularity at a fixed point

Summary. Local solutions of the functional equation¶¶z^k f( z) = ?_k=1ⁿG_k( z) f( s_kz ) +g( z) z{^\kappa} \phi \left( z\right) =\sum_{k=1}^nG_k\left( z\right) \phi \left( s_kz \right) +g\left( z\right) ¶with k > 0 \kappa > 0 and | s_k| \gt 1 \left| s_k\right| \gt 1 are considered. We prove that the equation is solvable if and only if a certain system of k \kappa conditions on G_k (k = 1, 2, ... , n) and g is fulfilled.     

Resonant destabilization of a floating homogeneous ice layer

We show that a homogeneous elastic ice layer of finite thickness and infinite horizontal extension floating on the surface of a homogeneous water layer of finite depth possesses a countable unbounded set of of resonant frequencies. The water is assumed to be compressible, the viscous effects are neglected in the model. Responses of this water-ice system to spatially localized harmonic in time perturbations with the resonant frequencies grow at least as ?t\sqrt{t} in the two-dimensional (2-D) case and at least as lnt in the three-dimensional (3-D) case, when time t?￥.t\to\infty. The analysis is based on treating the 3-D linear stability problem by applying the Laplace-Fourier transform and reducing the consideration to the 2-D case. The dispersion relation for the 2-D problem D(k,w) = 0,{D}(k,\omega) = 0, obtained previously by Brevdo and Il'ichev [10], is treated analytically and also computed numerically. Here k is a wavenumber, and w\omega is a frequency. It is proved that the system D(k,w) = 0, D_k(k,w) = 0{D}(k,\omega) = 0, {D}_k(k,\omega) = 0 possesses a countable unbounded set of roots (k, w) = (0,w_n), n ? \Bbb Z(k, \omega) = (0,\omega_n), n\in\Bbb Z with Im w_n = 0.\rm{Im}\ \omega_n = 0. Then the analysis of Brevdo [6], [7], [8], [9], which showed the existence of resonances in a homogeneous elastic waveguide, is applied to show that similar resonances exist in the present water-ice model. We propose a resonant mechanism for ice-breaking. It is based on destabilizing the floating ice layer by applying localized harmonic perturbations, with a moderate amplitude and at a resonant frequency.     

On q-Olivier Functions

We consider words w₁· · · w_n with letters w_i ? {1, 2, 3, ?} w_i \in \{1, 2, 3, \ldots\} satisfying an up-up-down pattern like a₁ h a₂ h a₃ S a₄ h a₅ h a₆ S · · · . Attaching the (geometric) probability pq^i-1 to the letter i (with p = 1 -- q), every word gets a probability by assuming independence of letters. We are interested in the probability that a random word of length n satisfies the up-up-down condition. It turns out that one has to consider the 3 residue classes (mod 3) separately; then one can compute the associated probability generating function. They turn out to be q-analogues of so called Olivier functions.     

On the number of conjugacy classes of maximal subgroups in a finite soluble group

We show that for many formations \frak F\frak F, there exists an integer n = [`(m)](\frak F)n = \overline m(\frak F) such that every finite soluble group G not belonging to the class \frak F\frak F has at most n conjugacy classes of maximal subgroups belonging to the class \frak F\frak F. If \frak F\frak F is a local formation with formation function f, we bound [`(m)](\frak F)\overline m(\frak F) in terms of the [`(m)](f(p))(p ? \Bbb P )\overline m(f(p))(p \in \Bbb P ). In particular, we show that [`(m)](\frak N^k) = k+1\overline m(\frak N^k) = k+1 for every nonnegative integer k, where \frak N^k\frak N^k is the class of all finite groups of Fitting length ￡ k\le k.     

Asymptotically autonomous parabolic evolution equations

We study the long-term behaviour of the parabolic evolution equation $\[u'(t)=A(t)u(t)+f(t), t>s,\quad u(s)=x. \]$\[u'(t)=A(t)u(t)+f(t), t>s,\quad u(s)=x. \] If A(t) A(t) converges to a sectorial operator A with s(A)?i \Bbb R = ? \sigma(A)\cap i \Bbb R =\emptyset as t?￥ t\to\infty , then the evolution family solving the homogeneous problem has exponential dichotomy. If also f(t)? f_￥ f(t)\to f_\infty , then the solution u converges to the 'stationary solution at infinity', i.e., lim_t?￥u(t) = -A\sp-1f_￥=:u_￥,        lim_t?￥u￠(t)=0,        lim_t?￥A(t)u(t)=Au_￥. \lim_{t\to\infty}u(t)= -A\sp{-1}f_\infty=:u_\infty, \qquad \lim_{t\to\infty}u'(t)=0, \qquad \lim_{t\to\infty}A(t)u(t)=Au_\infty. .     

Moser's second one-dimensional inequality for a class of integral operators

Suppose that $1 < p < \infty $1 < p < \infty , q=p/(p-1)q=p/(p-1), and for non-negative f ? L^p(-￥ ,￥)f\in L^p(-\infty\! ,\infty ) and any real x we let F(x)-F(0)=ò₀^xf(t) dtF(x)-F(0)=\int _0^xf(t)\ dt; suppose in addition that ò_-￥^￥ F(t)exp(-|t|) dt=0\int\limits _{-\infty }^\infty F(t)\exp (-|t|)\ dt=0. Moser's second one-dimensional inequality states that there is a constant C_pC_p, such that ò_-￥^￥ exp[a |F(x)|^q-|x|]  dx ￡ C_p\int\limits _{-\infty }^\infty \exp [a |F(x)|^q-|x|] \ dx\le C_p for each f with ||f||_p ￡ 1||f||_p\le 1 and every a ￡ 1a\le 1. Moreover the value a = 1 is sharp. We replace the operation connecting f with F by a more general integral operation; specifically we consider non-negative kernels K(t,x) with the property that xK(t,x) is homogeneous of degree 0 in t, x. We state an analogue of the inequality above for this situation, discuss some applications and consider the sharpness of the constant which replaces a.     

Representations of nilpotent Lie algebras

Let (L,[p]) a finite dimensional nilpotent restricted Lie algebra of characteristic p 3 3, c ? L^*p \geq 3, \chi \in L^* a linear form. In this paper we study the representation theory of the reduced universal enveloping algebra u(L,c)u(L,\chi ). It is shown that u(L,c)u(L,\chi ) does not admit blocks of tame representation type. As an application, we prove that the nonregular AR-components of u(L,c)u(L,\chi ) are of types \Bbb Z [A_￥ ]\Bbb Z [A_\infty ] or \Bbb Z [A_n]/(t)\Bbb Z [A_n]/(\tau ).     

Invariants of free Lie algebras

Let k be a principal ideal domain with identity and characteristic zero. For a positive integer n, with n \geqq 2n \geqq 2, let H(n) be the group of all n x n matrices having determinant ±1\pm 1. Further, we write SL(n) for the special linear group. Let L be a free Lie algebra (over k) of finite rank n. We prove that the algebra of invariants L^B(n) of B(n), with B(n) ? { H(n), SL(n)}B(n) \in \{ H(n), {\rm SL}(n)\} , is not a finitely generated free Lie algebra. Let us assume that k is a field of characteristic zero and let áSem(n) ?\langle {\rm Sem}(n) \rangle be the Lie subalgebra of L generated by the semi-invariants (or Lie invariants) Sem(n). We prove that áSem(n) ?\langle {\rm Sem}(n) \rangle is not a finitely generated free Lie algebra which gives a positive answer to a question posed by M. Burrow [4].     

On a class of non-uniform average sampling expansions and partial reconstruction in subspaces of L 2(?)

Let ϕ be a function in the Wiener amalgam space W_￥(L₁)\emph{W}_{\infty}(L_1) with a non-vanishing property in a neighborhood of the origin for its Fourier transform [^(f)]\widehat{\phi}, t={t_n}_{n ? \mathbb Z}{\bf \tau}=\{\tau_n\}_{n\in {{\mathbb Z}}} be a sampling set on ℝ and V_f^tV_\phi^{\bf \tau} be a closed subspace of L₂(\mathbbR)L_2(\hbox{\ensuremath{\mathbb{R}}}) containing all linear combinations of τ-translates of ϕ. In this paper we prove that every function f ? V_f^tf\in V_\phi^{\bf \tau} is uniquely determined by and stably reconstructed from the sample set L_f^t(f)={ò_\mathbbR f(t)[`(f(t-t_n))] dt}_{n ? \mathbb Z}L_\phi^{\bf \tau}(f)=\Big\{\int_{\hbox{\ensuremath{\mathbb{R}}}} f(t) \overline{\phi(t-\tau_n)} dt\Big\}_{n\in {{\mathbb Z}}}. As our reconstruction formula involves evaluating the inverse of an infinite matrix we consider a partial reconstruction formula suitable for numerical implementation. Under an additional assumption on the decay rate of ϕ we provide an estimate to the corresponding error.