A geometrical problem arising in a signal restoration algorithm

Let ℤ_2N={0, ..., 2N-1} denote the group of integers modulo 2N, and let L be the space of all real functions of ℤ_2N which are supported on {0,...N−1}. The spectral phase of a function f:ℤ_2N→ℝ is given by φ_f(k)=arg for k ∈ ℤ_2N, where denotes the discrete Fourier transforms of f. For a fixed s∈L let K_s denote the cone of all f:ℤ_2N→ℝ which satisfy φ_f ≡ φ_s and let M_s be its linear span. The angle α_s between M_s and L determines the convergence rate of the signal restoration from phase algorithm of Levi and Stark [3]. Here we prove the following conjectures of Urieli et al. [7] who verified them for the N≤3 case:

On exactlym times covers

In this paper it is shown that if every integer is covered bya ₁+n ₁ℤ,…,a _k +n _k ℤ exactlym times then for eachn=1,…,m there exist at least ( _n ^m ) subsetsI of {1,…k} such that ∑ _{i ∈ I} 1/n _i equalsn. The bound ( _n ^m ) is best possible. Research supported by the National Nature Science Foundation of P.R. of China.     

Sum Complexes—a New Family of Hypertrees

A k-dimensional hypertree X is a k-dimensional complex on n vertices with a full (k−1)-dimensional skeleton and \binomn-1k\binom{n-1}{k} facets such that H _k (X;ℚ)=0. Here we introduce the following family of simplicial complexes. Let n,k be integers with k+1 and n relatively prime, and let A be a (k+1)-element subset of the cyclic group ℤ _n . The sum complex X _A is the pure k-dimensional complex on the vertex set ℤ _n whose facets are σ⊂ℤ _n such that |σ|=k+1 and ∑ _x∈σ x∈A. It is shown that if n is prime, then the complex X _A is a k-hypertree for every choice of A. On the other hand, for n prime, X _A is k-collapsible iff A is an arithmetic progression in ℤ _n .     

The Erdős-Heilbronn problem in Abelian groups

Solving a problem of Erdős and Heilbronn, in 1994 Dias da Silva and Hamidoune proved that ifA is a set ofk residues modulo a primep,p≥2k−3, then the number of different elements of ℤ/pℤ that can be written in the forma+a′ wherea, a′ ∈A,a∈a′, is at least 2k−3. Here we extend this result to arbitrary Abelian groups in which the order of any nonzero element is at least 2k−3. Visiting the Rényi Institute of the Hungarian Academy of Sciences. Research partially supported by Hungarian Scientific Research Grants OTKA T043623 and T043631 and the CRM, University of Montreal.     

On the set of discrete subgroups of bounded covolume in a semisimple group

In this noteG is a locally compact group which is the product of finitely many groups G_s(k_s)(s∈S), where k_s is a local field of characteristic zero and G_s an absolutely almost simplek _s-group, ofk _s-rank ≥1. We assume that the sum of the r_s is ≥2 and fix a Haar measure onG. Then, given a constantc > 0, it is shown that, up to conjugacy,G contains only finitely many irreducible discrete subgroupsL of covolume ≥c (4.2). This generalizes a theorem of H C Wang for real groups. His argument extends to the present case, once it is shown thatL is finitely presented (2.4) and locally rigid (3.2).     

Kolmogorov and linear widths of classes of <Emphasis Type="Italic">s</Emphasis>-monotone integrable functions

Let s ∈ ℕ and let Δ ₊ ^s be the set of functions x: I ↦ ℝ on a finite interval I such that the divided differences [x; t ₀, ..., t _s ] of order s of these functions are nonnegative for all collections of s + 1 different points t ₀, ..., t _s ∈ I. For the classes Δ ₊ ^s B _p : = Δ ₊ ^s ∩ B _p , where B _p is the unit ball in L _p , we determine the orders of Kolmogorov and linear widths in the spaces _Lq for 1 ≤ q > p ≤ ∞. __________ Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 57, No. 12, pp. 1633–1652, December, 2005.     

On sums and products in ℂ[<Emphasis Type="Italic">x</Emphasis>]

We prove that there exists an absolute constant c>0 such that if A is a set of n monic polynomials, and if the product set A.A has at most n ^1+c elements, then |A+A|≫n2. This can be thought of as step towards proving the Erdős–Szemerédi sum-product conjecture for polynomial rings. We also show that under a suitable generalization of Fermat’s Last Theorem, the same result holds for the integers. The methods we use to prove are a mixture of algebraic (e.g. Mason’s theorem) and combinatorial (e.g. the Ruzsa–Plunnecke inequality) techniques.     

Irregular wavelet frames on<Emphasis Type="Italic">L</Emphasis><Superscript>2</Superscript>(ℝ<Superscript>n</Superscript>)

In this paper, we present the conditions on dilation parameter {s _j}_j that ensure a discrete irregular wavelet system {s _j ^n/2ψ(s _j ·−bk)} _{j∈ℤ,k∈ℤ} ⁿ to be a frame on L²(ℝⁿ), and for the wavelet frame we consider the perturbations of translation parameter b and frame function ψ respectively.     

Erdős measures,sofic measures,and Markov chains

We consider the random variable ζ = ξ₁ρ+ξ₂ρ²+…, where ξ₁, ξ₂, … are independent identically distibuted random variables taking the values 0 and 1 with probabilities P(ξ_i = 0) = p₀, P(ξ_i = 1) = p₁, 0 < p₀ < 1. Let β = 1/ρ be the golden number. The Fibonacci expansion for a random point ρζ from [0, 1] is of the form η₁ρ + η₂ρ² + … where the random variables η_k are {0, 1}-valued and η_kη_k+1 = 0. The infinite random word η = η₁η₂ … η_n … takes values in the Fibonacci compactum and determines the so-called Erdős measure μ(A) = P(η ∈ A) on it. The invariant Erdős measure is the shift-invariant measure with respect to which the Erdős measure is absolutely continuous. We show that the Erdős measures are sofic. Recall that a sofic system is a symbolic system that is a continuous factor of a topological Markov chain. A sofic measure is a one-block (or symbol-to-symbol) factor of the measure corresponding to a homogeneous Markov chain. For the Erdős measures, the corresponding regular Markov chain has 5 states. This gives ergodic properties of the invariant Erdős measure. We give a new ergodic theory proof of the singularity of the distribution of the random variable ζ. Our method is also applicable when ξ₁, ξ₂, … is a stationary Markov chain with values 0, 1. In particular, we prove that the distribution of ζ is singular and that the Erdős measures appear as the result of gluing together states in a regular Markov chain with 7 states. Bibliography: 3 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 326, 2005, pp. 28–47.     

The bieri-strebel invariant and homological finiteness conditions for metabelian groups

A group Γ has type F P_n if a trivial ℤΓ-module ℤ has a projective resolution P:…P_n → … → P₁ → P₀ → ℤ in which ℤΓ-module P_n,…P₁, P₀ are finitely generated. Let the finitely generated group Γ be a split extension of the Abelian group M by an Abelian group Q, suppose M is torsion free, and assume Γ∈F P_m, m≥2. Then the invariant ∑ _c ^M is m-tame. Translated fromAlgebra i Logika, Vol. 36, No. 2, pp. 194–218, March–April, 1997.     

Renormalization of multiple <Emphasis Type="Italic">q</Emphasis>-zeta values

In this paper, we shall define the renormalization of the multiple q-zeta values （MqZV） which are special values of multiple q-zeta functions ζq （s1,..., Sd） when the arguments are all positive integers or all non-positive integers. This generalizes the work of Guo and Zhang （Renormalization of Multiple Zeta Values, arxiv： math/0606076v3）. We show that our renormalization process produces the same values if the MqZVs are well-defined originally and that these renormalizations of MqZV satisfy the q-stuffle relations if we use shifted-renormalizations for all divergent ζq（S1,..., sd） （i.e., s1 ≤ 1）. Moreover, when q ↑ 1 our renormalizations agree with those of Guo and Zhang.     

On a problem of Erdős on integers, none of which divides the product of others

Erdős estimated the maximal number of integers selected from {1,2,…,N}, so that none of them divides the product of two others. In this paper, Erdős’ problem is extended to sets of integers such that none of them divides the product of k others. The proofs use combinatorial results.     

Large Deviation Principles for Moving Average Processes of Real Stationary Sequences

Let X _k =∑ _i=−∞^∞ a _i ξ _k−i ,k≥1, be the moving average processes, where (ξ _i ) _i∈ℤ is a sequence of real stationary random variables. Under the assumptions that the large deviation principle (LDP) for real stationary sequence holds, LDP for the moving average processes of real stationary sequence is established.      

Abelian group pairs having a trivial coGalois group

Torsion-free covers are considered for objects in the category q ₂. Objects in the category q ₂ are just maps in R-Mod. For R = ℤ, we find necessary and sufficient conditions for the coGalois group G(A → B), associated to a torsion-free cover, to be trivial for an object A → B in q ₂. Our results generalize those of E. Enochs and J. Rado for abelian groups.     

Sur le 2-groupe de classes d'idéaux de ℚ(√d,i)

Let ℕ,i=√−1,k=ℚ(√d,i) andC ₂ the 2-part of the class group ofk. Our goal is to determine alld such thatC ₂⋍ℤ/2ℤ×ℤ/2ℤ. Soientd∈ℕ,i=√−1,k=ℚ(√d,i), etC ₂ la 2-partie du groupe de classes dek. On s'intéresse à déterminer tous lesd tel queC ₂⋍ℤ/2ℤ×ℤ/2ℤ.      

On a problem of Cilleruelo and Nathanson

Let ℤ denote the set of all integers and ℕ the set of all positive integers. Let A be a set of integers. For every integer u, we denote by d _A (u) and s _A (u) the number of solutions of u=a − a′ with a,a′ ∈ A and u=a+a′ with a,a′ ∈ A and a≤a′, respectively.     

Positional Games and the Second Moment Method

Dedicated to the memory of Paul Erdős We study the fair Maker–Breaker graph Ramsey game MB(n;q). The board is , the players alternately occupy one edge a move, and Maker wants a clique of his own. We show that Maker has a winning strategy in MB(n;q) if , which is exactly the clique number of the random graph on n vertices with edge-probability 1/2. Due to an old theorem of Erdős and Selfridge this is best possible apart from an additive constant. Received March 28, 2000     

The Erdős–Pósa Property for Odd Cycles in Highly Connected Graphs

Dedicated to the memory of Paul Erdős In [9] Thomassen proved that a -connected graph either contains k vertex disjoint odd cycles or an odd cycle cover containing at most 2k-2 vertices, i.e. he showed that the Erdős–Pósa property holds for odd cycles in highly connected graphs. In this paper, we will show that the above statement is still valid for 576k-connected graphs which is essentially best possible. Received November 17, 1999 RID="*" ID="*" This work was supported by a post-doctoral DONET grant. RID="†" ID="†" This work was supported by an NSF-CNRS collaborative research grant. RID="‡" ID="‡" This work was performed while both authors were visiting the LIRMM, Université de Montpellier II, France.     

Van der corput’s difference theorem

We obtain a sufficient condition for a subsetH of positive integers to satisfy that the equidistribution (mod 1) of the sequences (u _n+h − u _n; n=1, 2, ···) for allh ∈H implies the equidistribution of (u _n). Our condition is satisfied, for example, for the following sets: (1)H={n − m; n ∈ I, m ∈ I, n>m}, whereI is any infinite subset of integers; (2)H={| ψ (n)|; ψ(n)≠0,n ∈ Z}, where ψ is a nonconstant polynomial with integral coefficients having at least one integral zero (modq) for allq=2, 3, ···; (3)H={p+1;p is a prime} andH={p − 1;p is a prime}.     

Regular subgraphs of dense graphs

Every graph onn vertices, with at leastc _k n logn edges contains ak-regular subgraph. This answers a question of Erdős and Sauer.