Positive values of non-homogeneous indefinite quadratic forms of type (1, 4)

Let Г_r,n—r denote the infimum of all number Г > 0 such that for any real indefinite quadratic form inn variables of type (r, n—r), determinantD ≠ 0 and real numbers c₁; c₂,…, c_n, there exist integersx ₁,x₂,…,x_n satisfying 0 < Q(x₁+c₁,x₂ + c₂,…,x_n + c_n) ≤(Г|Z > |)^1/n. All the values of Г_r,n—r are known except for г_1,4. Earlier it was shown that 8 ≤Г_1,4 ≤16. Here we improve the upper bound to get Г_1,4 < 12.     

On the Construction of Permutation Arrays via Mappings from Binary Vectors to Permutations

An (n, d, k)-mapping f is a mapping from binary vectors of length n to permutations of length n + k such that for all x, y {0,1}ⁿ, d_H (f(x), f(y)) ≥ d_H (x, y) + d, if d_H (x, y) ≤ (n + k) − d and d_H (f(x), f(y)) = n + k, if d_H (x, y) > (n + k) − d. In this paper, we construct an (n,3,2)-mapping for any positive integer n ≥ 6. An (n, r)-permutation array is a permutation array of length n and any two permutations of which have Hamming distance at least r. Let P(n, r) denote the maximum size of an (n, r)-permutation array and A(n, r) denote the same setting for binary codes. Applying (n,3,2)-mappings to the design of permutation array, we can construct an efficient permutation array (easy to encode and decode) with better code rate than previous results [Chang (2005). IEEE Trans inf theory 51:359–365, Chang et al. (2003). IEEE Trans Inf Theory 49:1054–1059; Huang et al. (submitted)]. More precisely, we obtain that, for n ≥ 8, P(n, r) ≥ A(n − 2, r − 3) > A(n − 1,r − 2) = A(n, r − 1) when n is even and P(n, r) ≥ A(n − 2, r − 3) = A(n − 1, r − 2) > A(n, r − 1) when n is odd. This improves the best bound A(n − 1,r − 2) so far [Huang et al. (submitted)] for n ≥ 8. The work was supported in part by the National Science Council of Taiwan under contract NSC-93-2213-E-009-117     

Large holes in sparse random graphs

We show that there is a function α(r) such that for each constantr≧3, almost everyr-regular graph onn vertices has a hole (vertex induced cycle) of size at least α(r)n asn→∞. We also show that there is a function β(c) such that forc>0 large enough,G _{n, p} ,p=c/n almost surely has a hole of size at least β(c)n asn→∞.     

Distribution of points on spheres and approximation by zonotopes

It is proved that if we approximate the Euclidean ballB ⁿ in the Hausdorff distance up toɛ by a Minkowski sum ofN segments, then the smallest possibleN is equal (up to a possible logarithmic factor) toc(n)ε ^{−2(n−1)/(n+2)}. A similar result is proved ifB ⁿ is replaced by a general zonoid inR ⁿ .     

Integrals and Banach spaces for finite order distributions

Let B _c denote the real-valued functions continuous on the extended real line and vanishing at −∞. Let B _r denote the functions that are left continuous, have a right limit at each point and vanish at −∞. Define A _c ⁿ to be the space of tempered distributions that are the nth distributional derivative of a unique function in B _c . Similarly with A _r ⁿ from B _r . A type of integral is defined on distributions in A _c ⁿ and A _r ⁿ . The multipliers are iterated integrals of functions of bounded variation. For each n ∈ ℕ, the spaces A _c ⁿ and A _r ⁿ are Banach spaces, Banach lattices and Banach algebras isometrically isomorphic to B _c and B _r , respectively. Under the ordering in this lattice, if a distribution is integrable then its absolute value is integrable. The dual space is isometrically isomorphic to the functions of bounded variation. The space A _c ¹ is the completion of the L ¹ functions in the Alexiewicz norm. The space A _r ¹ contains all finite signed Borel measures. Many of the usual properties of integrals hold: H?lder inequality, second mean value theorem, continuity in norm, linear change of variables, a convergence theorem.     

New upper bounds for the Davenport and for the Erdős–Ginzburg–Ziv constants

Let G be a finite abelian group (written additively) of rank r with invariants n ₁, n ₂, . . . , n _r , where n _r is the exponent of G. In this paper, we prove an upper bound for the Davenport constant D(G) of G as follows; D(G) ≤ n _r + n _r-1 + (c(3) − 1)n _r-2 + (c(4) − 1) n _r-3 + · · · + (c(r) − 1)n ₁ + 1, where c(i) is the Alon–Dubiner constant, which depends only on the rank of the group \mathbb Z_nrⁱ{{\mathbb Z}_{n_r}^i}. Also, we shall give an application of Davenport’s constant to smooth numbers related to the Quadratic sieve.     

Maximum Hitting of a Set by Compressed Intersecting Families

For a family A{\mathcal{A}} and a set Z, denote {A ? A \colon A ?Z 1 ?}{\{A \in \mathcal{A} \colon A \cap Z \neq \emptyset\}} by A(Z){\mathcal{A}(Z)}. For positive integers n and r, let S_n,r{\mathcal{S}_{n,r}} be the trivial compressed intersecting family {A ? (c[n]r ) \colon 1 ? A}{\{A \in \big(\begin{subarray}{c}[n]\\r \end{subarray}\big) \colon 1 \in A\}}, where [n] : = {1, ?, n}{[n] := \{1, \ldots, n\}} and (c[n]r ) : = {A ì [n] \colon |A| = r}{\big(\begin{subarray}{c}[n]\\r \end{subarray}\big) := \{A \subset [n] \colon |A| = r\}}. The following problem is considered: For r ≤ n/2, which sets Z í [n]{Z \subseteq [n]} have the property that |A(Z)| ￡ |S_n,r(Z)|{|\mathcal{A}(Z)| \leq |\mathcal{S}_{n,r}(Z)|} for any compressed intersecting family A ì (c[n]r ){\mathcal{A}\subset \big(\begin{subarray}{c}[n]\\r \end{subarray}\big)}? (The answer for the case 1 ? Z{1 \in Z} is given by the Erdős–Ko–Rado Theorem.) We give a complete answer for the case |Z| ≥ r and a partial answer for the much harder case |Z| < r. This paper is motivated by the observation that certain interesting results in extremal set theory can be proved by answering the question above for particular sets Z. Using our result for the special case when Z is the r-segment {2, ?, r+1}{\{2, \ldots, r+1\}}, we obtain new short proofs of two well-known Hilton–Milner theorems. At the other extreme end, by establishing that |A(Z)| ￡ |S_n,r(Z)|{|\mathcal{A}(Z)| \leq |\mathcal{S}_{n,r}(Z)|} when Z is a final segment, we provide a new short proof of a Holroyd–Talbot extension of the Erdős-Ko-Rado Theorem.     

Discretization of Compact Riemannian Manifolds Applied to the Spectrum of Laplacian

For κ ⩾ 0 and r₀ > 0 let ℳ(n, κ, r₀) be the set of all connected, compact n-dimensional Riemannian manifolds (Mⁿ, g) with Ricci (M, g) ⩾ −(n−1) κ g and Inj (M) ⩾ r₀. We study the relation between the kth eigenvalue λ_k(M) of the Laplacian associated to (Mⁿ,g), Δ = −div(grad), and the kth eigenvalue λ_k(X) of a combinatorial Laplacian associated to a discretization X of M. We show that there exist constants c, C > 0 (depending only on n, κ and r₀) such that for all M ∈ ℳ(n, κ, r₀) and X a discretization of for all k < |X|. Then, we obtain the same kind of result for two compact manifolds M and N ∈ ℳ(n, κ, r₀) such that the Gromov–Hausdorff distance between M and N is smaller than some η > 0. We show that there exist constants c, C > 0 depending on η, n, κ and r₀ such that for all . Mathematics Subject Classification (2000): 58J50, 53C20 Supported by Swiss National Science Foundation, grant No. 20-101 469     

The brouwer fixed point theorem and tetragon with all vertexes in a surface

LetD be a disc with radiusr in the Euclidean plane ℝ², and letF be a Lipschitz continuous real valued function onD. SupposeA ₁ A ₂₁ A ₃ A ₄ is an isosceles trapezoid with lengths of edges not greater thanr, and ∠A ₁ A ₂₁ A ₃ = α≤π/2 By means of the Brouwer fixed point theorem, it is proved that ifF has a Lipschitz constant λ≤min{1, tgα}, then there exist four coplanar points in the surfaceM = {(x, y, F(x, y))∈ℝ³:(x, y)ℝ} which span a tetragon congruent toA ₁ A ₂₁ A ₃ A ₄. In addition, some further problems are discussed. Project supported by the National Natural Science Foundation of China (Grant No. 19231201).     

Some connected ramsey numbers

A graph G is co-connected if both G and its complement ? are connected and nontrivial. For two graphs A and B, the connected Ramsey number r_c(A, B) is the smallest integer n such that there exists a co-connected graph of order n, and if G is a co-connected graph on at least n vertices, then A ? G or B ? ?. If neither A or B contains a bridge, then it is known that r_c(A, B) = r(A, B), where r(A, B) denotes the usual Ramsey number of A and B. In this paper r_c(A, B) is calculated for some pairs (A, B) when r(A, B) is known and at least one of the graphs A or B has a bridge. In particular, r_c(A, B) is calculated for A a path and B either a cycle, star, or complete graph, and for A a star and B a complete graph.     

SO（n）-Invariant Special Lagrangian Submanifolds of C^n＋l with Fixed Loci

Abstract Let SO(n) act in the standard way on ℂⁿ and extend this action in the usual way to ℂⁿ⁺¹ = ℂ ⊕ ℂⁿ. It is shown that a nonsingular special Lagrangian submanifold L ⊂ ℂⁿ⁺¹ that is invariant under this SO(n)-action intersects the fixed ℂ ⊂ ℂⁿ⁺¹ in a nonsingular real-analytic arc A (which may be empty). If n > 2, then A has no compact component. Conversely, an embedded, noncompact nonsingular real-analytic arc A ⊂ ℂ lies in an embedded nonsingular special Lagrangian submanifold that is SO(n)-invariant. The same existence result holds for compact A if n = 2. If A is connected, there exist n distinct nonsingular SO(n)-invariant special Lagrangian extensions of A such that any embedded nonsingular SO(n)-invariant special Lagrangian extension of A agrees with one of these n extensions in some open neighborhood of A. The method employed is an analysis of a singular nonlinear PDE and ultimately calls on the work of Gérard and Tahara to prove the existence of the extension. * Project supported by Duke University via a research grant, the NSF via DMS-0103884, the Mathematical Sciences Research Institute, and Columbia University. (Dedicated to the memory of Shiing-Shen Chern, whose beautiful works and gentle encouragement have had the most profound influence on my own research)     

Covering Complete Hypergraphs with Cuts of Minimum Total Size

A cut [X, V − X] in a hypergraph with vertex-set V is the set of all edges that meet both X and V − X. Let s _r (n) denote the minimum total size of any cover of the edges of the complete r-uniform hypergraph on n vertices K_n^r{K_n^r} by cuts. We show that there is a number n _r such that for every n > n _r , s _r (n) is uniquely achieved by a cover with ?\fracn-1r-1?{\lfloor \frac{n-1}{r-1}\rfloor} cuts [X _i , V − X _i ] such that the X _i are pairwise disjoint sets of size at most r − 1. We show that c₁r2^r < n_r < c₂r⁵2^r{c_1r2^r < n_r < c_2r^52^r} for some positive absolute constants c ₁ and c ₂. Using known results for s ₂(n) we also determine s ₃(n) exactly for all n.     

Completely positive maps and*-isomorphism ofC *-algebras II

LetA, B be unitalC ^*-algebras,D _A ¹ the set of all completely positive maps ϕ fromA toM _n (C), with Tr ϕ(I)≤1(n≥3). If Ψ is an α-invariant affine homeomorphism betweenD _A ¹ andD _B ¹ with Ψ (0)=0, thenA is^*-isomorphic toB. Obtained results can be viewed as non-commutative Kadison-Shultz theorems. This work is supported by the National Natural Science Foundation of China.     

On the order of growth of solutions of algebraic differential equations

Assume thatf is an integer transcendental solution of the differential equationP _n (z, f, f′)=P _n−1(z, f, f′, ... f ^(p)), whereP _n andP _n−1 are polynomials in all variables, the degree ofP _n with respect tof andf′ is equal ton, and the degree ofP _n−1 with respect tof, f′, ... f ^(p) is at mostn−1. We prove that the order ρ of growth off satisfies the relation 1/2≤ρ<∞. We also prove that if ρ=1/2, then, for a certain real ν, in the domain {z: ν<argz<ν+2π}/E _*, whereE _* is a certain set of disks with finite sum of radii, the estimate lnf(z)=z ^1/2 (β+o(1)), β∈C, holds forz=re ^iϕ,r≥r(ϕ)≥0. Furthermore, on the ray {z: argz=ν}, the following relation is true: ln‖f(re ^iν)‖=o(r ^1/2),r→+∞,r>0, , where Δ is a certain set on the semiaxisr>0 with mes Δ<∞. “L'vivs'ka Politekhnika” University, Lvov. Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 51, No. 1, pp. 69–77, January, 1999.     

Operator algebras and a theorem of Dieudonne

LetA be aC*-algebra with second dualA″. Let (φ _n)(n=1,...) be a sequence in the dual ofA such that limφ _n(a) exists for eacha εA. In general, this does not imply that limφ _n(x) exists for eachx εA″. But if limφ _n(p) exists whenever p is the range projection of a positive self-adjoint element of the unit ball ofA, then it is shown that limφ _n(x) does exist for eachx inA″. This is a non-commutative generalisation of a celebrated theorem of Dieudonné. A new proof of Dieudonné’s theorem, for positive measures, is given here. The proof of the main result makes use of Dieudonné’s original theorem.     

On Order Types of Systems of Segments in the Plane

Let r(n) denote the largest integer such that every family C\mathcal{C} of n pairwise disjoint segments in the plane in general position has r(n) members whose order type can be represented by points. Pach and Tóth gave a construction that shows r(n) < n ^log8/log9 (Pach and Tóth 2009). They also stated that one can apply the Erdős–Szekeres theorem for convex sets in Pach and Tóth (Discrete Comput Geom 19:437–445, 1998) to obtain r(n) > log₁₆ n. In this note, we will show that r(n) > cn ^1/4 for some absolute constant c.     

On a reduced load equivalence for fluid queues under subexponentiality

We propose a general framework for obtaining asymptotic distributional bounds on the stationary backlog in a buffer fed by a combined fluid process A ₁ + A ₂ and drained at a constant rate c. The fluid process A ₁ is an (independent) on–off source with average and peak rates ρ₁ and r₁ , respectively, and with distribution G for the activity periods. The fluid process A ₂ of average rate ρ₂ is arbitrary but independent of A ₁. These bounds are used to identify subexponential distributions G and fairly general fluid processes A ₂ such that the asymptotic equivalence P[W ^A1+A2,c >ϰ]∼P[W ^A1,c—ρ2>ϰ] (ϰ → ∞) holds under the stability condition ρ₁ + ρ₂ < c and the non-triviality condition c – ρ₂ < r ₁. In these asymptotics the stationary backlog results from feeding source A ₁ into a buffer drained at reduced rate c – ρ₂. This reduced load asymptotic equivalence extends to a larger class of distributions G a result obtained by Jelenkovic and Lazar [19] in the case when G belongs to the class of regular intermediate varying distributions. This revised version was published online in June 2006 with corrections to the Cover Date.     

Algébres topologiquement uniformes et algébres fortement topologiquement uniformes

We characterize locally convex topological algebrasA satisfying: a sequence (x _n) inA converges to 0 if, and only if, (x _n ²) converges to 0. We also show that a real Banach algebra such thatx _n ²+y _n ²→0 if, and only if,x _n → 0 andy _n → 0, for every sequences (x _n) and (y _n) inA, is isomorphic to, whereX is a compact space.      

A note on Sobolev orthogonality for Laguerre matrix polynomials

Let {Ln(A,λ)(x)}n≥0 be the sequence of monic Laguerre matrix polynomials defined on [0, ∞) by Ln(A,λ)(x)=n!/(-λ)n∑nk=0(-λ)κ/k!(n-1)! (A I)n[(A I)k]-1 xk,where A ∈ Cr×r. It is known that {Ln(A,λ)(x)}n≥0 is orthogonal with respect to a matrix moment functional when A satisfies the spectral condition that Re(z) ＞ - 1 for every z ∈σ(A).In this note we show that forA such that σ(A) does not contain negative integers, the Laguerre matrix polynomials Ln(A,λ) (x) are orthogonal with respect to a non-diagonal SobolevLaguerre matrix moment functional, which extends two cases: the above matrix case and the known scalar case.     

Counting the number of twin Niven numbers

Given an integer q≥2, we say that a positive integer is a q-Niven number if it is divisible by the sum of its digits in base q. Given an arbitrary integer r∈[2,2q], we say that (n,n+1,…,n+r−1) is a q-Niven r -tuple if each number n+i, for i=0,1,…,r−1, is a q-Niven number. We show that there exists a positive constant c=c(q,r) such that the number of q-Niven r-tuples whose leading component is <x is asymptotic to cx/(log x) ^r as x→∞. Research of J.M. De Koninck supported in part by a grant from NSERC. Research of I. Kátai supported by the Applied Number Theory Research Group of the Hungarian Academy of Science and by a grant from OTKA.