Groups with weak maximality condition for nonnilpotent subgroups

A group G satisfies the weak maximality condition for nonnilpotent subgroups [or, briefly, the Wmax-(nonnil) condition if G does not have infinite increasing chains {H _n | n ∈ ℕ} of nonnilpotent subgroups such that the indices |H _n+1: H _n | are infinite for each n ∈ ℕ. We study the structure of hypercentral groups satisfying the weak maximality condition for nonnilpotent subgroups. __________ Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 58, No. 8, pp. 1068–1083, August, 2006.     

Representation of measurable functions by series in Walsh subsystems

For any sequence {ω(n)} _n∈ℕ tending to infinity we construct a “quasiquadratic” representation spectrum Λ = {n ² + o(ω(n))} _n∈ℕ: for any almost everywhere (a. e.) finite measurable function f(x) there exists a series in the form $ \mathop \sum \limits_{k \in \Lambda } $ \mathop \sum \limits_{k \in \Lambda } α _k ω _k (x) that converges a. e. to this function, where {w _k (x)} _k∈ℕ is the Walsh system. We find representation spectra in the form {n ^l + o(n ^l )} _n∈ℕ, where l ∈ {2 ^k } _k∈ℕ.     

Digital representation of semigroups and groups

A digital representation of a semigroup (S,⋅) is a family 〈F _t 〉 _t∈I , where I is a linearly ordered set, each F _t is a finite non-empty subset of S and every element of S is uniquely representable in the form Π _t∈H   x _t where H is a finite subset of I, each x _t ∈F _t and products are taken in increasing order of indices. (If S has an identity 1, then Π _t∈∅   x _t =1.) A strong digital representation of a group G is a digital representation of G with the additional property that for each t∈I, for some x _t ∈G and some m _t >1 in ℕ where m _t =2 if the order of x _t is infinite, while, if the order of x _t is finite, then m _t is a prime and the order of x _t is a power of m _t . We show that any free semigroup has a digital representation with each | F _t |=1 and that each Abelian group has a strong digital representation. We investigate the problem of whether all groups, or even all finite groups have strong digital representations, obtaining several partial results. Finally, we give applications to the algebra of the Stone-Čech compactification of a discrete group and the weakly almost periodic compactification of a discrete semigroup. Dedicated to Karl Heinrich Hofmann on the occasion of his 75th birthday. Stefano Ferri was partially supported by a research grant of the Faculty of Sciences of Universidad de los Andes. The support is gratefully acknowledged. Neil Hindman acknowledges support received from the National Science Foundation via Grant DMS-0554803.     

Asymptotic results on infinite tandem queueing networks

We consider an infinite tandem queueing network consisting of ·/GI/1/∞ stations with i.i.d. service times. We investigate the asymptotic behavior of t(n, k), the inter-arrival times between customers n and n + 1 at station k, and that of w(n, k), the waiting time of customer n at station k. We establish a duality property by which w(n, k) and the “idle times”y(n, k) play symmetrical roles. This duality structure, interesting by itself, is also instrumental in proving some of the ergodic results. We consider two versions of the model: the quadrant and the half-plane. In the quadrant version, the sequences of boundary conditions {w(0,k), k∈ℕ} and {t(n, 0), n∈ℕ}, are given. In the half-plane version, the sequence {t(n, 0), n∈ℕ} is given. Under appropriate assumptions on the boundary conditions and on the services, we obtain ergodic results for both versions of the model. For the quadrant version, we prove the existence of temporally ergodic evolutions and of spatially ergodic ones. Furthermore, the process {t(n, k), n∈ℕ} converges weakly with k to a limiting distribution, which is invariant for the queueing operator. In the more difficult half plane problem, the aim is to obtain evolutions which are both temporally and spatially ergodic. We prove that 1/n∑ _k=1 ⁿ w(0, k) converges almost surely and in L ₁ to a finite constant. This constitutes a first step in trying to prove that {t(n,k), n∈ℤ} converges weakly with k to an invariant limiting distribution. Received: 23 March 1999 / Revised version: 5 January 2000 / Published online: 12 October 2000     

Equidistribution of sparse sequences on nilmanifolds

We study equidistribution properties of nil-orbits (b ⁿ x) _n∈ℕ when the parameter n is restricted to the range of some sparse sequence that is not necessarily polynomial. For example, we show that if X = G/Γ is a nilmanifold, b ∈ G is an ergodic nilrotation, and c ∈ ℝ \ ℤ is positive, then the sequence $ (b^{[n^c ]} x)_{n \in \mathbb{N}} $ (b^{[n^c ]} x)_{n \in \mathbb{N}} is equidistributed in X for every x ∈ X. This is also the case when n ^c is replaced with a(n), where a(t) is a function that belongs to some Hardy field, has polynomial growth, and stays logarithmically away from polynomials, and when it is replaced with a random sequence of integers with sub-exponential growth. Similar results have been established by Boshernitzan when X is the circle.     

On one extremal problem for numerical series

Let Γ be the set of all permutations of the natural series and let α = {α _j} _j∈ℕ, ν = {ν_j} _j∈ℕ, and η = {η_j} _j∈ℕ be nonnegative number sequences for which

Algebras whose equivalence relations are congruences

It is proved that all the equivalence relations of a universal algebra A are its congruences if and only if either |A| ≤ 2 or every operation f of the signature is a constant (i.e., f(a ₁ , . . . , a _n ) = c for some c ∈ A and all the a ₁ , . . . , a _n ∈ A) or a projection (i.e., f(a ₁ , . . . , a _n ) = a _i for some i and all the a ₁ , . . . , a _n ∈ A). All the equivalence relations of a groupoid G are its right congruences if and only if either |G| ≤ 2 or every element a ∈ G is a right unit or a generalized right zero (i.e., x _a  = y _a for all x, y ∈ G). All the equivalence relations of a semigroup S are right congruences if and only if either |S| ≤ 2 or S can be represented as S = A∪B, where A is an inflation of a right zero semigroup, and B is the empty set or a left zero semigroup, and ab = a, ba = a ² for a ∈ A, b ∈ B. If G is a groupoid of 4 or more elements and all the equivalence relations of it are right or left congruences, then either all the equivalence relations of the groupoid G are left congruences, or all of them are right congruences. A similar assertion for semigroups is valid without the restriction on the number of elements.     

Asymptotic behaviour of trajectories of unipotent flows on homogeneous spaces

We show that ifG is a semisimple algebraic group defined overQ and Γ is an arithmetic lattice inG:=G _R with respect to theQ-structure, then there exists a compact subsetC ofG/Γ such that, for any unipotent one-parameter subgroup {u _t} ofG and anyg∈G, the time spent inC by the {u _t}-trajectory ofgΓ, during the time interval [0,T], is asymptotic toT, unless {g ⁻¹u_tg} is contained in aQ-parabolic subgroup ofG. Some quantitative versions of this are also proved. The results strengthen similar assertions forSL(n,Z),n≥2, proved earlier in [5] and also enable verification of a technical condition introduced in [7] for lattices inSL(3,R), which was used in our proof of Raghunathan’s conjecture for a class of unipotent flows, in [8].     

To the problem of a strong differentiability of integrals along different directions

It is proved that for any given sequence (σ _n ,n ∈ ℕ)=Γ₀ ⊂ Γ, where Γ is the set of all directions in ℝ² (i.e., pairs of orthogonal straight lines) there exists a locally integrable functionf on ℝ² such that: (1) for almost all directionsσ ∈ Γ\Γ₀ the integral ∫f is differentiable with respect to the familyB _2σ of open rectangles with sides parallel to the straight lines fromσ: (2) for every directionσ _n ∈ Γ₀ the upper derivative of ∫f with respect toB _{2σ n} equals +∞; (3) for every directionσ ∈ Γ the upper derivative of ∫ |f| with respect toB _2σ equals +∞.     

Non-wandering points and the depth for graph maps

Let G be a graph and f:G→G be continuous.Denote by R(f) andΩ(f) the set of recurrent points and the set of non-wandering points of f respectively.LetΩ_0(f) = G andΩ_n(f)=Ω(f|_(Ω_(n-1)(f))) for all n∈N.The minimal m∈NU {∞} such thatΩ_m(f)=Ω_(m 1)(f) is called the depth of f.In this paper,we show thatΩ_2 (f)=(?) and the depth of f is at most 2.Furthermore,we obtain some properties of non-wandering points of f.     

A descent method for submodular function minimization

We show a descent method for submodular function minimization based on an oracle for membership in base polyhedra. We assume that for any submodular function f: ?→R on a distributive lattice ?⊆2 ^V with ?,V∈? and f(?)=0 and for any vector x∈R ^V where V is a finite nonempty set, the membership oracle answers whether x belongs to the base polyhedron associated with f and that if the answer is NO, it also gives us a set Z∈? such that x(Z)>f(Z). Given a submodular function f, by invoking the membership oracle O(|V|²) times, the descent method finds a sequence of subsets Z ₁,Z ₂,···,Z _k of V such that f(Z ₁)>f(Z ₂)>···>f(Z _k )=min{f(Y) | Y∈?}, where k is O(|V|²). The method furnishes an alternative framework for submodular function minimization if combined with possible efficient membership algorithms. Received: September 9, 2001 / Accepted: October 15, 2001?Published online December 6, 2001     

Optimal properties of contraction semigroups in banach spaces

Suppose that(T _t )_t>0 is aC ₀ semi-group of contractions on a Banach spaceX, such that there exists a vectorx∈X, ‖x‖=1 verifyingJ ⁻¹(Jx)={x}, whereJ is the duality mapping fromX toP(X ^*). If |<T _t x,f>|→1, whent→+∞ for somef∈X ^*, ‖f‖≤1 thenx is an eigenvector of the generatorA, associated with a purcly imaginary eigenvalue. Because of Lin's example [L], the hypothesis onx∈X is the best possible. If the hypothesisJ ⁻¹(Jx)={x} is not verified, we can prove that ifJx is a singleton and ifJ ⁻¹(Jx) is weakly compact, then if |<T _t x, f>|→1, whent→+∞ for somef∈X ^*, ‖f‖≤1, there existsy∈J ⁻¹(Jx) such thaty is an eigenvector of the generatorA, associated with a purely imaginary eigenvalue. We give also a counter-example in the case whereX is one of the spaces ℓ₁ orL ₁.     

Factors and Connected Induced Subgraphs

 Let G be a connected graph without loops and without multiple edges, and let p be an integer such that 0 < p<|V(G)|. Let f be an integer-valued function on V(G) such that 2≤f(x)≤ deg _G (x) for all x∈V(G). We show that if every connected induced subgraph of order p of G has an f-factor, then G has an f-factor, unless ∑ _{x ∈ V ( G )} f(x) is odd. Received: June 29, 1998?Final version received: July 30, 1999     

Transversals of additive Latin squares

LetA={a ₁, …,a _k} andB={b ₁, …,b _k} be two subsets of an Abelian groupG, k≤|G|. Snevily conjectured that, whenG is of odd order, there is a permutationπ ∈S _ksuch that the sums α _i +b _i , 1≤i≤k, are pairwise different. Alon showed that the conjecture is true for groups of prime order, even whenA is a sequence ofk<|G| elements, i.e., by allowing repeated elements inA. In this last sense the result does not hold for other Abelian groups. With a new kind of application of the polynomial method in various finite and infinite fields we extend Alon’s result to the groups (ℤ _p ) ^a and in the casek<p, and verify Snevily’s conjecture for every cyclic group of odd order. Supported by Hungarian research grants OTKA F030822 and T029759. Supported by the Catalan Research Council under grant 1998SGR00119. Partially supported by the Hungarian Research Foundation (OTKA), grant no. T029132.     

On thin-complete ideals of subsets of groups

Let F ì P_G \mathcal{F} \subset {\mathcal{P}_G} be a left-invariant lower family of subsets of a group G. A subset A ⊂ G is called F \mathcal{F} -thin if xA ?yA ? F xA \cap yA \in \mathcal{F} for any distinct elements x, y ∈ G. The family of all F \mathcal{F} -thin subsets of G is denoted by t( F ) \tau \left( \mathcal{F} \right) . If t( F ) = F \tau \left( \mathcal{F} \right) = \mathcal{F} , then F \mathcal{F} is called thin-complete. The thin-completion t^*( F ) {\tau^*}\left( \mathcal{F} \right) of F \mathcal{F} is the smallest thin-complete subfamily of P_G {\mathcal{P}_G} that contains F \mathcal{F} . Answering questions of Lutsenko and Protasov, we prove that a set A ⊂ G belongs to τ*(G) if and only if, for any sequence (g _n ) _n∈ω of nonzero elements of G, there is n ∈ ω such that

Tame Sets in the Complement of Algebraic Variety

Let A?? ^N be an algebraic variety with dim?A≤N?2. Given discrete sequences {a _j },{b _j }?? ^N \ A with slow growth ( $\sum_{j}{1\over|a_{j}|^{2}}<\infty,\sum_{j}{1\over |b_{j}|^{2}}<\inftyLet A⊂ℂ ^N be an algebraic variety with dim A≤N−2. Given discrete sequences {a _j },{b _j }⊂ℂ ^N \ A with slow growth ( ?_j[1/(|a_j|²)] < ￥,?_j[1/(|b_j|²)] < ￥\sum_{j}{1\over|a_{j}|^{2}}<\infty,\sum_{j}{1\over |b_{j}|^{2}}<\infty ) we construct a holomorphic automorphism F with F(z)=z for all z∈A and F(a _j )=b _j for all j∈ℕ. Additional approximation of a given automorphism on a compact polynomially convex set, fixing A, is also possible. Given unbounded analytic variety A there is a tame set E such that F(E)≠{(j,0 ^N−1):j∈ℕ} for all automorphisms F with F| _A =id. As an application we obtain an embedding of a Stein manifold into the complement of an algebraic variety in ℂ ^N with interpolation on a given discrete set.     

Gersgorin variations II: On themes of Fan and Gudkov

Assume F={f₁,. . .,f_n} is a family of nonnegative functions of n−1 nonnegative variables such that, for every matrix A of order n, |a_ii|>f_i (moduli of off-diagonal entries in row i of A) for all i implies A nonsingular. We show that there is a positive vector x, depending only on F, such that for all A=(a_ij), and all i, f_i≥∑_j|a_ij|{x_j}/x_i. This improves a theorem of Ky Fan, and yields a generalization of a nonsingularity criterion of Gudkov. Dedicated to Charles A. Micchelli, in celebration of his 60th birthday and our 30 years of friendship     

Linear equations and sets of integers

We prove two results concerning solvability of a linear equation in sets of integers. In particular, it is shown that for every k∈ℕ, there is a noninvariant linear equation in k variables such that if A⫅{1,…,N} has no solution to the equation then |A|\leqq 2^-ck/(logk)2N|A|\leqq 2^{-ck/{(\log k)}^{2}}N, for some absolute constant c>0, provided that N is large enough.     

Optimal Three Cylinder Inequality at the Boundary for Solutions to Parabolic Equations and Unique Continuation Properties

Let Γ be a portion of a C ^1,α boundary of an n-dimensional domain D. Let u be a solution to a second order parabolic equation in D × (–T, T) and assume that u = 0 on Γ × (–T, T), 0 ∈ Γ. We prove that u satis.es a three cylinder inequality near Γ × (–T, T) . As a consequence of the previous result we prove that if u (x, t) = O (|x|^k) for every t ∈ (–T, T) and every k ∈ ℕ, then u is identically equal to zero. This work is partially supported by MURST, Grant No. MM01111258     

Multiparameter inverse problem of approximation by functions with given supports

Let L _p (S), 0 < p < +∞, be a Lebesgue space of measurable functions on S with ordinary quasinorm ∥·∥ _p . For a system of sets {B _t |t ∈ [0, +∞) ⁿ } and a given function ψ: [0, +∞) ⁿ ↦ [ 0, +∞), we establish necessary and sufficient conditions for the existence of a function f ∈ L _p (S) such that inf {∥f − g∥ _p ^p g ∈ L _p (S), g = 0 almost everywhere on S\B _t } = ψ (t), t ∈ [0, +∞) ⁿ . As a consequence, we obtain a generalization and improvement of the Dzhrbashyan theorem on the inverse problem of approximation by functions of the exponential type in L ₂. __________ Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 58, No. 8, pp. 1116–1127, August, 2006.