Lower Bounds for Dimensions of Sums of Sets

We study lower bounds for the Minkowski and Hausdorff dimensions of the algebraic sum E+K of two sets E,K⊂ℝ ^d .     

Decomposition Algorithm Model for Singly Linearly-Constrained Problems Subject to Lower and Upper Bounds

Many real applications can be formulated as nonlinear minimization problems with a single linear equality constraint and box constraints. We are interested in solving problems where the number of variables is so huge that basic operations, such as the evaluation of the objective function or the updating of its gradient, are very time consuming. Thus, for the considered class of problems (including dense quadratic programs), traditional optimization methods cannot be applied directly. In this paper, we define a decomposition algorithm model which employs, at each iteration, a descent search direction selected among a suitable set of sparse feasible directions. The algorithm is characterized by an acceptance rule of the updated point which on the one hand permits to choose the variables to be modified with a certain degree of freedom and on the other hand does not require the exact solution of any subproblem. The global convergence of the algorithm model is proved by assuming that the objective function is continuously differentiable and that the points of the level set have at least one component strictly between the lower and upper bounds. Numerical results on large-scale quadratic problems arising in the training of support vector machines show the effectiveness of an implemented decomposition scheme derived from the general algorithm model.     

Absorbing Angles,Steiner Minimal Trees,and Antipodality

We give a new proof that a star {op _i :i=1,…,k} in a normed plane is a Steiner minimal tree of vertices {o,p ₁,…,p _k } if and only if all angles formed by the edges at o are absorbing (Swanepoel in Networks 36: 104–113, 2000). The proof is simpler and yet more conceptual than the original one. We also find a new sufficient condition for higher-dimensional normed spaces to share this characterization. In particular, a star {op _i :i=1,…,k} in any CL-space is a Steiner minimal tree of vertices {o,p ₁,…,p _k } if and only if all angles are absorbing, which in turn holds if and only if all distances between the normalizations \frac1||p_i||p_i\frac{1}{\Vert p_{i}\Vert}p_{i} equal 2. CL-spaces include the mixed ℓ ₁ and ℓ _∞ sum of finitely many copies of ℝ.     

Lower Bounds for the Wiener Norm in ℤpd

Mathematical Notes - We obtain lower bounds for the ℓ1-norm of the Fourier transform of functions on ℤpd.     

Upper and Lower Bounds for Probabilities in the Conditional Borel–Cantelli Lemma

We obtain an inequality connected with a conditional version of the generalized Borel–Cantelli lemma.     

Lower Bounds for the Difference ax n − by m

In this work we give completely explicit lower bounds for |ax ⁿ – by ^m | depending only on a, b, n, m and a, b, n, x, respectively.     

Some Lower Bounds in the B. and M. Shapiro Conjecture for Flag Varieties

The B. and M. Shapiro conjecture stated that all solutions of the Schubert Calculus problems associated with real points on the rational normal curve should be real. For Grassmannians, it was proved by Mukhin, Tarasov, and Varchenko. For flag varieties, Sottile found a counterexample and suggested that all solutions should be real under certain monotonicity conditions. In this paper, we compute lower bounds on the number of real solutions for some special cases of the B. and M. Shapiro conjecture for flag varieties, when Sottile’s monotonicity conditions are not satisfied.     

Logarithmic Dimension Bounds for the Maximal Function Along a Polynomial Curve

Let ℳ denote the maximal function along the polynomial curve (γ ₁ t,…,γ _d t ^d ):

On Fast Polynomial Algorithms and Lower Bounds of the Linear Complexity

ＯｎＦａｓｔＰｏｌｙｎｏｍｉａｌＡｌｇｏｒｉｔｈｍｓａｎｄＬｏｗｅｒＢｏｕｎｄｓｏｆｔｈｅＬｉｎｅａｒＣｏｍｐｌｅｘｉｔｙＬｉＬｅｉ（李磊）（Ｘｉ＇ａｎＪｉａｏｔｏｎｇＵｎｉｖｅｒｓｉｔｙ，Ｘｉ＇ａｎ，Ｃｈｉｎａ，＆ＡｏｍｏｒｉＵｎｉｖｅｒｓｉｔｙ，...     

On Energy, Discrepancy and Group Invariant Measures on Measurable Subsets of Euclidean Space

Given $\mathcal{X}Given X\mathcal{X}, some measurable subset of Euclidean space, one sometimes wants to construct a finite set of points, P ì X\mathcal{P}\subset\mathcal {X}, called a design, with a small energy or discrepancy. Here it is shown that these two measures of design quality are equivalent when they are defined via positive definite kernels K:X²(=X×X)?\mathbbRK:\mathcal{X}^{2}(=\mathcal{X}\times\mathcal {X})\to\mathbb{R}. The error of approximating the integral ò_Xf(x) dm(x)\int_{\mathcal{X}}f(\boldsymbol{x})\,\mathrm{d}\mu(\boldsymbol{x}) by the sample average of f over P\mathcal{P} has a tight upper bound in terms of the energy or discrepancy of P\mathcal{P}. The tightness of this error bound follows by requiring f to lie in the Hilbert space with reproducing kernel K. The theory presented here provides an interpretation of the best design for numerical integration as one with minimum energy, provided that the measure μ defining the integration problem is the equilibrium measure or charge distribution corresponding to the energy kernel, K.     

Uniformly Accurate Quantile Bounds for Sums of Arbitrary Independent Random Variables

Fix any n≥1. Let X ₁,…,X _n be independent random variables such that S _n =X ₁+⋅⋅⋅+X _n , and let S^*_n=sup_{1 ￡ k ￡ n}S_kS^{*}_{n}=\sup_{1\le k\le n}S_{k} . We construct upper and lower bounds for s _y and s_y^*s_{y}^{*} , the upper \frac1y\frac{1}{y} th quantiles of S _n and S^*_nS^{*}_{n} , respectively. Our approximations rely on a computable quantity Q _y and an explicit universal constant γ _y , the latter depending only on y, for which we prove that

Convergent Bounds for Stochastic Programs with Expected Value Constraints

This article describes a bounding approximation scheme for convex multistage stochastic programs (MSP) that constrain the conditional expectation of some decision-dependent random variables. Expected value constraints of this type are useful for modelling a decision maker’s risk preferences, but they may also arise as artifacts of stage-aggregation. We develop two finite-dimensional approximate problems that provide bounds on the (infinite-dimensional) original problem, and we show that the gap between the bounds can be made smaller than any prescribed tolerance. Moreover, the solutions of the approximate MSPs give rise to a feasible policy for the original MSP, and this policy’s optimality gap is shown to be smaller than the difference of the bounds. The considered problem class comprises models with integrated chance constraints and conditional value-at-risk constraints. No relatively complete recourse is assumed.     

Burgess-like Subconvex Bounds for GL2 × GL1

Let F be a number field, π an irreducible cuspidal representation of \({{\rm GL}_2(\mathbb{A}_F)}\) with unitary central character, and χ a Hecke character of analytic conductor Q. Then \({L(1/2, \pi \otimes \chi) \ll Q^{\frac{1}{2} - \frac{1}{8}(1-2\theta)+\epsilon}}\) , where \({0 \leq \theta \leq 1/2}\) is any exponent towards the Ramanujan–Petersson conjecture. The proof is based on an idea of unipotent translation originated from P. Sarnak then developed by Ph. Michel and A. Venkatesh, combined with a method of amplification.     

Growth and Integrability of Fourier Transforms on Euclidean Space

A fundamental theme in classical Fourier analysis relates smoothness properties of functions to the growth and/or integrability of their Fourier transform. By using a suitable class of \(L^{p}\) -multipliers, a rather general inequality controlling the size of Fourier transforms for large and small argument is obtained. As consequences, quantitative Riemann–Lebesgue estimates are obtained and an integrability result for the Fourier transform is developed extending ideas used by Titchmarsh in the one dimensional setting.     

Symmetries,Lagrangian and Conservation Laws for the Maxwell Equations

The evolution equations of Maxwell’s equations has a Lagrangian written in terms of the electric E and magnetic H fields, but admit neither Lorentz nor conformal transformations. The additional equations ∇⋅E=0, ∇⋅H=0 guarantee the Lorentz and conformal invariance, but the resulting system is overdetermined, and hence does not have a Lagrangian. The aim of the present paper is to attain a harmony between these two contradictory properties and provide a correspondence between symmetries and conservation laws using the Lagrangian for the evolutionary part of Maxwell’s equations.     

Connectivity properties of horospheres in Euclidean buildings and applications to finiteness properties of discrete groups

Let G(O_S)\mathbf{G}(\mathcal{O}_{S}) be an S-arithmetic subgroup of a connected, absolutely almost simple linear algebraic group G over a global function field K. We show that the sum of local ranks of G determines the homological finiteness properties of G(O_S)\mathbf{G}(\mathcal{O}_{S}) provided the K-rank of G is 1. This shows that the general upper bound for the finiteness length of G(O_S)\mathbf{G}(\mathcal{O}_{S}) established in an earlier paper is sharp in this case.     

A Generalization of Opsut’s Lower Bounds for the Competition Number of a Graph

The notion of a competition graph was introduced by Cohen in 1968. The competition graph C(D) of a digraph D is a (simple undirected) graph which has the same vertex set as D and has an edge between two distinct vertices x and y if and only if there exists a vertex v in D such that (x, v) and (y, v) are arcs of D. For any graph G, G together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. In 1978, Roberts defined the competition number k(G) of a graph G as the minimum number of such isolated vertices. In general, it is hard to compute the competition number k(G) for a graph G and it has been one of the important research problems in the study of competition graphs to characterize a graph by its competition number. In 1982, Opsut gave two lower bounds for the competition number of a graph. In this paper, we give a generalization of these two lower bounds for the competition number of a graph.