Greedy Algorithm Computing Minkowski Reduced Lattice Bases with Quadratic Bit Complexity of Input Vectors

The authors present an algorithm which is a modification of the Nguyen-Stehle greedy reduction algorithm due to Nguyen and Stehle in 2009. This algorithm can be used to compute the Minkowski reduced lattice bases for arbitrary rank lattices with quadratic bit complexity on the size of the input vectors. The total bit complexity of the algorithm is $O(n^2 \cdot (4n!)^n \cdot (\tfrac{{n!}} {{2^n }})^{\tfrac{n} {2}} \cdot (\tfrac{4} {3})^{\tfrac{{n(n - 1)}} {4}} \cdot (\tfrac{3} {2})^{\tfrac{{n^2 (n - 1)}} {2}} \cdot \log ^2 A) $O(n^2 \cdot (4n!)^n \cdot (\tfrac{{n!}} {{2^n }})^{\tfrac{n} {2}} \cdot (\tfrac{4} {3})^{\tfrac{{n(n - 1)}} {4}} \cdot (\tfrac{3} {2})^{\tfrac{{n^2 (n - 1)}} {2}} \cdot \log ^2 A) , where n is the rank of the lattice and A is maximal norm of the input base vectors. This is an O(log² A) algorithm which can be used to compute Minkowski reduced bases for the fixed rank lattices. A time complexity n! · 3 ⁿ (log A) ^O(1) algorithm which can be used to compute the successive minima with the help of the dual Hermite-Korkin-Zolotarev base was given by Blomer in 2000 and improved to the time complexity n! · (log A) ^O(1) by Micciancio in 2008. The algorithm in this paper is more suitable for computing the Minkowski reduced bases of low rank lattices with very large base vector sizes.     

On the trigonometric polynomials of Fejér and Young

The trigonometric polynomials of Fejér and Young are defined by $S_n (x) = \sum\nolimits_{k = 1}^n {\tfrac{{\sin (kx)}} {k}}$S_n (x) = \sum\nolimits_{k = 1}^n {\tfrac{{\sin (kx)}} {k}} and $C_n (x) = 1 + \sum\nolimits_{k = 1}^n {\tfrac{{\cos (kx)}} {k}}$C_n (x) = 1 + \sum\nolimits_{k = 1}^n {\tfrac{{\cos (kx)}} {k}}, respectively. We prove that the inequality $\left( {{1 \mathord{\left/ {\vphantom {1 9}} \right. \kern-\nulldelimiterspace} 9}} \right)\sqrt {15} \leqslant {{C_n \left( x \right)} \mathord{\left/ {\vphantom {{C_n \left( x \right)} {S_n \left( x \right)}}} \right. \kern-\nulldelimiterspace} {S_n \left( x \right)}}$\left( {{1 \mathord{\left/ {\vphantom {1 9}} \right. \kern-\nulldelimiterspace} 9}} \right)\sqrt {15} \leqslant {{C_n \left( x \right)} \mathord{\left/ {\vphantom {{C_n \left( x \right)} {S_n \left( x \right)}}} \right. \kern-\nulldelimiterspace} {S_n \left( x \right)}} holds for all n ≥ 2 and x ∈ (0, π). The lower bound is sharp.     

An addition theorem and maximal zero-sum free sets in ℤ/<Emphasis Type="Italic">p</Emphasis>ℤ

Using the polynomial method in additive number theory, this article establishes a new addition theorem for the set of subsums of a set satisfying A ∩ (−A) = ∅ in ℤ/pℤ:

On the chromatic number of random geometric graphs

Given independent random points X ₁,...,X _n ∈ℝ ^d with common probability distribution ν, and a positive distance r=r(n)>0, we construct a random geometric graph G _n with vertex set {1,..., n} where distinct i and j are adjacent when ‖X _i −X _j ‖≤r. Here ‖·‖ may be any norm on ℝ ^d , and ν may be any probability distribution on ℝ ^d with a bounded density function. We consider the chromatic number χ(G _n ) of G _n and its relation to the clique number ω(G _n ) as n→∞. Both McDiarmid [11] and Penrose [15] considered the range of r when $r \ll \left( {\tfrac{{\ln n}} {n}} \right)^{1/d}$r \ll \left( {\tfrac{{\ln n}} {n}} \right)^{1/d} and the range when $r \gg \left( {\tfrac{{\ln n}} {n}} \right)^{1/d}$r \gg \left( {\tfrac{{\ln n}} {n}} \right)^{1/d}, and their results showed a dramatic difference between these two cases. Here we sharpen and extend the earlier results, and in particular we consider the ‘phase change’ range when $r \sim \left( {\tfrac{{t\ln n}} {n}} \right)^{1/d}$r \sim \left( {\tfrac{{t\ln n}} {n}} \right)^{1/d} with t>0 a fixed constant. Both [11] and [15] asked for the behaviour of the chromatic number in this range. We determine constants c(t) such that $\tfrac{{\chi (G_n )}} {{nr^d }} \to c(t)$\tfrac{{\chi (G_n )}} {{nr^d }} \to c(t) almost surely. Further, we find a “sharp threshold” (except for less interesting choices of the norm when the unit ball tiles d-space): there is a constant t ₀>0 such that if t≤t ₀ then $\tfrac{{\chi (G_n )}} {{\omega (G_n )}}$\tfrac{{\chi (G_n )}} {{\omega (G_n )}} tends to 1 almost surely, but if t>t ₀ then $\tfrac{{\chi (G_n )}} {{\omega (G_n )}}$\tfrac{{\chi (G_n )}} {{\omega (G_n )}} tends to a limit >1 almost surely.     

Stability of symmetric closed characteristics on symmetric compact convex hypersurfaces in ℝ<Superscript>2<Emphasis Type="Italic">n</Emphasis></Superscript> under a pinching condition

In this paper, let Σ R2n be a symmetric compact convex hypersurface which is ( r, R )- pinched with R/r (5/3)1/2 . Then Σ carries at least two elliptic symmetric closed characteristics; moreover, Σ carries at least E [ n-1/2 ] + E [ n-1/3 ] non-hyperbolic symmetric closed characteristics.     

Fujita-Liouville Type Theorem for Coupled Fourth-Order Parabolic Inequalities

This paper deals with a coupled system of fourth-order parabolic inequalities |u|t ≥ 2u + |v|q,|v|t ≥ 2v + |u|p in S = Rn × R+ with p,q > 1,n ≥ 1.A FujitaLiouville type theorem is established that the inequality system does not admit nontrivial nonnegative global solutions on S whenever n4 ≤ max(ppq+11,pqq+11).Since the general maximum-comparison principle does not hold for the fourth-order problem,the authors use the test function method to get the global non-existence of nontrivial solutions.     

Joint asymptotic distribution of exceedances point process and partial sum of stationary Gaussian sequence

Let {X _i } _i=1^∞ be a standardized stationary Gaussian sequence with covariance function r(n) = EX ₁ X _n+1, S _n = Σ _i=1 ⁿ X _i , and $\bar X_n = \tfrac{{S_n }} {n} $\bar X_n = \tfrac{{S_n }} {n} . And let N _n be the point process formed by the exceedances of random level $(\tfrac{x} {{\sqrt {2\log n} }} + \sqrt {2\log n} - \tfrac{{\log (4\pi \log n)}} {{2\sqrt {2\log n} }})\sqrt {1 - r(n)} + \bar X_n $(\tfrac{x} {{\sqrt {2\log n} }} + \sqrt {2\log n} - \tfrac{{\log (4\pi \log n)}} {{2\sqrt {2\log n} }})\sqrt {1 - r(n)} + \bar X_n by X ₁,X ₂,…, X _n . Under some mild conditions, N _n and S _n are asymptotically independent, and N _n converges weakly to a Poisson process on (0,1].     

Complete moment and integral convergence for sums of negatively associated random variables

For a sequence of identically distributed negatively associated random variables {Xn; n ≥ 1} with partial sums Sn = ∑i=1^n Xi, n ≥ 1, refinements are presented of the classical Baum-Katz and Lai complete convergence theorems. More specifically, necessary and sufficient moment conditions are provided for complete moment convergence of the form ∑n≥n0 n^r-2-1/pq anE（max1≤k≤n｜Sk｜^1/q-∈bn^1/qp）^＋〈∞to hold where r 〉 1, q 〉 0 and either n0 = 1,0 〈 p 〈 2, an = 1,bn = n or n0 = 3,p = 2, an = 1 （log n） ^1/2q, bn=n log n. These results extend results of Chow and of Li and Spataru from the indepen- dent and identically distributed case to the identically distributed negatively associated setting. The complete moment convergence is also shown to be equivalent to a form of complete integral convergence.     

Into how many regions do <Emphasis Type="Italic">n</Emphasis> lines divide the plane if at most <Emphasis Type="Italic">n − k</Emphasis> of them are concurrent?

The number of connected components of the complement in the real projective plane to a family of n ≥2 different lines such that any point belongs to at most n − k of them is estimated. If $ n \geqslant \frac{{k^2 + k}} {2} + 3 $ n \geqslant \frac{{k^2 + k}} {2} + 3 , then the number of regions is at least (k+1)(n−k). Thus, a new proof of N. Martinov’s theorem is obtained. This theorem determines all pairs of integers (n, f) such that there is an arrangement of n lines dividing the projective plane into f regions.     

Convergence rates of the LIL for random fields in Hilbert spaces

Considering the positive d-dimensional lattice point Z ₊ ^d (d ≥ 2) with partial ordering ≤, let {X _k: k ∈ Z ₊ ^d } be i.i.d. random variables taking values in a real separable Hilbert space (H, ‖ · ‖) with mean zero and covariance operator Σ, and set $ S_n = \sum\limits_{k \leqslant n} {X_k } $ S_n = \sum\limits_{k \leqslant n} {X_k } , n ∈ Z ₊ ^d . Let σ _i ², i ≥ 1, be the eigenvalues of Σ arranged in the non-increasing order and taking into account the multiplicities. Let l be the dimension of the corresponding eigenspace, and denote the largest eigenvalue of Σ by σ ². Let logx = ln(x ∨ e), x ≥ 0. This paper studies the convergence rates for $ \sum\limits_n {\frac{{\left( {\log \log \left| n \right|} \right)^b }} {{\left| n \right|\log \left| n \right|}}} P\left( {\left\| {S_n } \right\| \geqslant \sigma \varepsilon \sqrt {2\left| n \right|\log \log \left| n \right|} } \right) $ \sum\limits_n {\frac{{\left( {\log \log \left| n \right|} \right)^b }} {{\left| n \right|\log \left| n \right|}}} P\left( {\left\| {S_n } \right\| \geqslant \sigma \varepsilon \sqrt {2\left| n \right|\log \log \left| n \right|} } \right) . We show that when l ≥ 2 and b > −l/2, E[‖X‖²(log ‖X‖) ^d−2(log log ‖X‖) ^b+4] < ∞ implies $ \begin{gathered} \mathop {\lim }\limits_{\varepsilon \searrow \sqrt {d - 1} } (\varepsilon ^2 - d + 1)^{b + l/2} \sum\limits_n {\frac{{\left( {\log \log \left| n \right|} \right)^b }} {{\left| n \right|\log \left| n \right|}}P\left( {\left\| {S_n } \right\| \geqslant \sigma \varepsilon \sqrt 2 \left| n \right|\log \log \left| n \right|} \right)} \hfill \\ = \frac{{K(\Sigma )(d - 1)^{\frac{{l - 2}} {2}} \Gamma (b + l/2)}} {{\Gamma (l/2)(d - 1)!}} \hfill \\ \end{gathered} $ \begin{gathered} \mathop {\lim }\limits_{\varepsilon \searrow \sqrt {d - 1} } (\varepsilon ^2 - d + 1)^{b + l/2} \sum\limits_n {\frac{{\left( {\log \log \left| n \right|} \right)^b }} {{\left| n \right|\log \left| n \right|}}P\left( {\left\| {S_n } \right\| \geqslant \sigma \varepsilon \sqrt 2 \left| n \right|\log \log \left| n \right|} \right)} \hfill \\ = \frac{{K(\Sigma )(d - 1)^{\frac{{l - 2}} {2}} \Gamma (b + l/2)}} {{\Gamma (l/2)(d - 1)!}} \hfill \\ \end{gathered} , where Γ(·) is the Gamma function and $ \prod\limits_{i = l + 1}^\infty {((\sigma ^2 - \sigma _i^2 )/\sigma ^2 )^{ - {1 \mathord{\left/ {\vphantom {1 2}} \right. \kern-\nulldelimiterspace} 2}} } $ \prod\limits_{i = l + 1}^\infty {((\sigma ^2 - \sigma _i^2 )/\sigma ^2 )^{ - {1 \mathord{\left/ {\vphantom {1 2}} \right. \kern-\nulldelimiterspace} 2}} } .     

On <Emphasis Type="Italic">T</Emphasis> points of algebroid functions

In this paper, we firstly give a new definition, namely, the T point of algebroid functions. Then by using Ahlfors’ theory of covering surfaces, we prove the existence of these points for any ν-valued algebroid functions in the unit disk satisfying $\mathop {\lim \sup }\limits_{r \to 1^ - } \frac{{T(r,w)}} {{\log \tfrac{1} {{1 - r}}}} = + \infty $\mathop {\lim \sup }\limits_{r \to 1^ - } \frac{{T(r,w)}} {{\log \tfrac{1} {{1 - r}}}} = + \infty . This extends the recent results of Xuan, Wu and Sun.     

On zero sum subsequences of restricted size

Let G be a finite abelian group with exp(G) = e. Let s(G) be the minimal integer t with the property that any sequence of t elements in G contains an e-term subsequence with sum zero. Let n, mand r be positive integers and m ≥ 3. Furthermore, η(C _m ^r ) = a _r (m − 1) + 1, for some constant a _r depending on r and n is a fixed positive integer such that

Estimates of the capacity of orthogonal arrays of large strength

D.G. Fon-Der-Flaass showed that Boolean correlation-immune n-variable functions of order m are resilient for $ m \geqslant \frac{{2n - 2}} {3} $ m \geqslant \frac{{2n - 2}} {3} . In this paper this theorem is generalized to orthogonal arrays. It is shown that orthogonal arrays of strength m not less than $ \frac{{2n - 2}} {3} $ \frac{{2n - 2}} {3} , where n is a number of factors having size at least 2 ⁿ⁻¹ and all arrays of size 2 ⁿ⁻¹, are simple.     

Diffeomorphism classification of smooth weighted complete intersections

Xn(d1, . . . , dr-1, dr; w) and Xn(e1, . . . , er-1, dr; w) are two complex odd-dimensional smooth weighted complete intersections defined in a smooth weighted hypersurface Xn+r-1(dr; w). We prove that they are diffeomorphic if and only if they have the same total degree d, the Pontrjagin classes and the Euler characteristic, under the following assumptions: the weights w = (ω0, . . . , ωn+r) are pairwise relatively prime and odd, νp(d/dr) ≥ 2n+1/ 2(p-1) + 1 for all primes p with p(p-1) ≤ n + 1, where νp(d/dr) satisfies d/dr =Ⅱp prime pνp (d/dr).     

On the synthesis of oriented contact circuits with certain restrictions on adjacent contacts

Realization of Boolean functions in the class of oriented contact circuits (OCCs) with certain restrictions on the weight, number, and types of adjacent contacts is studied. Oriented contact circuits are considered in which, from an arbitrary vertex, at most λ arcs issue and at most ν different Boolean variables are used in the marks of the issuing arcs. The weight of a vertex of an OCC is defined as being equal to λ if one arc enters a vertex and equal to λ(1 + ω), where ω > 0, otherwise. Then, as usual, the weight of an OCC is defined as the sum of the weights of its vertices; the weight of a Boolean function, as the minimum weight of OCCs realizing it; and Shannon function W _{λ, ν, ω}(n), as the maximum weight of the Boolean function of n variables. For this Shannon function, the so-called high-accuracy bound

Bulk universality holds in measure for compactly supported measures

Let μ be a measure with compact support, with orthonormal polynomials {p _n } and associated reproducing kernels {K _n }. We show that bulk universality holds in measure in {ξ: μ′(ξ) > 0}. More precisely, given ɛ, r > 0, the linear Lebesgue measure of the set {ξ: μ′(ξ) > 0} and for which

The area of an exponential random walk and partial sums of uniform order statistics

Let S_i be a random walk with standard exponential increments. The sum ∑ _i=1 ^k S_i is called the k-step area of the walk. The random variable ∑ _i=1 ^k S_i plays an important role in the study of the so-called one-dimensional sticky particles model. We find the distribution of this variable and prove that

Uniform boundedness of (<Emphasis Type="Italic">C</Emphasis>, 1) means of Jacobi expansions in weighted sup norms. II (Some necessary estimations)

The paper is concerned with bounds for integrals of the type

On rigidity of Clifford torus in a unit sphere

We extend the scalar curvature pinching theorems due to Peng-Terng, Wei-Xu and Suh-Yang. Let M be an n-dimensional compact minimal hypersurface in S n+1 satisfying Sf 4 f_3~2 ≤ 1/n S~3 , where S is the squared norm of the second fundamental form of M, and f_k =sum λ_i~k from i and λ_i (1 ≤ i ≤ n) are the principal curvatures of M. We prove that there exists a positive constant δ(n)(≥ n/2) depending only on n such that if n ≤ S ≤ n + δ(n), then S ≡ n, i.e., M is one of the Clifford torus S~k ((k/n)~1/2 ) ×S~...     

A separation theorem and Serre duality for the Dolbeault cohomology

LetX be a complex manifold with finitely many ends such that each end is eitherq-concave or (n−q)-convex. If , then we prove thatH ^pn−q (X) is Hausdorff for allp. This is not true in general if (Rossi’s example withn=2 andq=1). If all ends areq-concave, then this is the classical Andreotti-Vesentini separation theorem (and holds also for ). Moreover the result was already known in the case when theq-concave ends can be ‘filled in’ (again also for ). To prove the result we first have to study Serre duality for the case of more general families of supports (instead of the family of all closed sets and the family of all compact sets) which is the main part of the paper. At the end we give an application to the extensibility of CR-forms of bidegree (p, q) from (n−q)-convex boundaries, . This research was partially supported by TMR Research Network ERBFMRXCT 98063.