Rate of Approximation of Regular Convex Bodies by?Convex Algebraic Level Surfaces

We consider the problem of the approximation of regular convex bodies in ℝ ^d by level surfaces of convex algebraic polynomials. Hammer (in Mathematika 10, 67–71, 1963) verified that any convex body in ℝ ^d can be approximated by a level surface of a convex algebraic polynomial. In Jaen J. Approx. 1, 97–109, 2009 and subsequently in J. Approx. Theory 162, 628–637, 2010 a quantitative version of Hammer’s approximation theorem was given by showing that the order of approximation of convex bodies by convex algebraic level surfaces of degree n is \frac1n\frac{1}{n}. Moreover, it was also shown that whenever the convex body is not regular (that is, there exists a point on its boundary at which the convex body possesses two distinct supporting hyperplanes), then \frac1n\frac{1}{n} is essentially the sharp rate of approximation. This leads to the natural question whether this rate of approximation can be improved further when the convex body is regular. In this paper we shall give an affirmative answer to this question. It turns out that for regular convex bodies a o(1/n) rate of convergence holds. In addition, if the body satisfies the condition of C ²-smoothness the rate of approximation is O(\frac1n²)O(\frac{1}{n^{2}}).     

Voronovskaja-Type Results in Compact Disks for Quaternion q-Bernstein Operators, q ≥ 1

Attaching to a compact disk [`(\mathbbD<sub>r</sub>)]{\overline{\mathbb{D}_{r}}} in the quaternion field \mathbbH{\mathbb{H}} and to some analytic function in Weierstrass sense on [`(\mathbbD_r)]{\overline{\mathbb{D}_{r}}} the so-called q-Bernstein operators with q ≥ 1, Voronovskaja-type results with quantitative upper estimates are proved. As applications, the exact orders of approximation in [`(\mathbbD_r)]{\overline{\mathbb{D}_{r}}} for these operators, namely \frac1n{\frac{1}{n}} if q = 1 and \frac1qⁿ{\frac{1}{q^{n}}} if q > 1, are obtained. The results extend those in the case of approximation of analytic functions of a complex variable in disks by q-Bernstein operators of complex variable in Gal (Mediterr J Math 5(3):253–272, 2008) and complete the upper estimates obtained for q-Bernstein operators of quaternionic variable in Gal (Approximation by Complex Bernstein and Convolution-Type Operators, 2009; Adv Appl Clifford Alg, doi:, 2011).     

On the Expected Probability of Constraint Violation in Sampled Convex Programs

In this note, we derive an exact expression for the expected probability V of constraint violation in a sampled convex program (see Calafiore and Campi in Math. Program. 102(1):25–46, 2005; IEEE Trans. Autom. Control 51(5):742–753, 2006 for definitions and an introduction to this topic):

Local well-posedness for the space–time Monopole equation in Lorenz gauge

It is known from Czubak (Anal PDE 3(2):151–174, 2010) that the space–time Monopole equation is locally well-posed in the Coulomb gauge for small initial data in H^s(\mathbbR²){H^s(\mathbb{R}^2)} for ${s>\frac{1}{4}}${s>\frac{1}{4}}. Here we prove local well-posedness for arbitrary initial data in H^s(\mathbbR²){H^s(\mathbb{R}^2)} with ${s>\frac{1}{4}}${s>\frac{1}{4}} in the Lorenz gauge.     

The Alexander-Orbach conjecture holds in high dimensions

We examine the incipient infinite cluster (IIC) of critical percolation in regimes where mean-field behavior has been established, namely when the dimension d is large enough or when d>6 and the lattice is sufficiently spread out. We find that random walk on the IIC exhibits anomalous diffusion with the spectral dimension d_s=\frac43d_{s}=\frac{4}{3} , that is, p _t (x,x)=t ^−2/3+o(1). This establishes a conjecture of Alexander and Orbach (J. Phys. Lett. (Paris) 43:625–631, 1982). En route we calculate the one-arm exponent with respect to the intrinsic distance.     

An Almost Sure Limit Theorem for Super-Brownian Motion

We establish an almost sure scaling limit theorem for super-Brownian motion on ℝ ^d associated with the semi-linear equation u_t=\frac12Du+bu-au²u_{t}=\frac{1}{2}\Delta u+\beta u-\alpha u^{2} , where α and β are positive constants. In this case, the spectral theoretical assumptions required in Chen et al. (J. Funct. Anal. 254:1988–2019, 2008) are not satisfied. An example is given to show that the main results also hold for some sub-domains in ℝ ^d .     

The $(1-\mathbb{E})$-transform in combinatorial Hopf algebras

We extend to several combinatorial Hopf algebras the endomorphism of symmetric functions sending the first power-sum to zero and leaving the other ones invariant. As a “transformation of alphabets”, this is the (1-\mathbbE)(1-\mathbb{E})-transform, where \mathbbE\mathbb{E} is the “exponential alphabet,” whose elementary symmetric functions are e_n=\frac1n!e_{n}=\frac{1}{n!}. In the case of noncommutative symmetric functions, we recover Schocker’s idempotents for derangement numbers (Schocker, Discrete Math. 269:239–248, 2003). From these idempotents, we construct subalgebras of the descent algebras analogous to the peak algebras and study their representation theory. The case of WQSym leads to similar subalgebras of the Solomon–Tits algebras. In FQSym, the study of the transformation boils down to a simple solution of the Tsetlin library in the uniform case.     

Quadratic fields with noncyclic 5- or 7-class groups

We shall show that the number of quadratic fields with absolute discriminant ≤x and noncyclic 5- or 7-class group is ≫x ^1/4 improving the existing known bound for g=5 and for g=7 in Byeon (Ramanujan J. 11:159–163, 2006). This work was supported by KRF-2005-070-C00004.     

Partitioning planar graphs: a?fast combinatorial approach for max-cut

The max-cut problem asks for partitioning the nodes V of a graph G=(V,E) into two sets (one of which might be empty), such that the sum of weights of edges joining nodes in different partitions is maximum. Whereas for general instances the max-cut problem is NP-hard, it is polynomially solvable for certain classes of graphs. For planar graphs, there exist several polynomial-time methods determining maximum cuts for arbitrary choice of edge weights. Typically, the problem is solved by computing a minimum-weight perfect matching in some associated graph. The most efficient known algorithms are those of Shih et al. (IEEE Trans. Comput. 39(5):694–697, 1990) and that of Berman et al. (WADS, Lecture Notes in Computer Science, vol. 1663, pp. 25–36, Springer, Berlin, 1999). The running time of the former can be bounded by O(|V|^\frac32log|V|)O(|V|^{\frac{3}{2}}\log|V|). The latter algorithm is more generally for determining T-joins in graphs. Although it has a slightly larger bound on the running time of O(|V|^\frac32(log|V|)^\frac32)a(|V|)O(|V|^{\frac{3}{2}}(\log|V|)^{\frac{3}{2}})\alpha(|V|), where α(|V|) is the inverse Ackermann function, it can solve large instances in practice.     

A characterisation result on a particular class of non-weighted minihypers

We present a characterisation of {e₁ (q+1)+e₀,e₁ ;n,q}{\{\epsilon_1 (q+1)+\epsilon_0,\epsilon_1 ;n,q\}} -minihypers, q square, q = p ^h , p > 3 prime, h ≥ 2, q ≥ 1217, for e₀ + e₁ < \fracq^7/122-\fracq^1/42{\epsilon_0 + \epsilon_1 < \frac{q^{7/12}}{2}-\frac{q^{1/4}}{2}}. This improves a characterisation result of Ferret and Storme (Des Codes Cryptogr 25(2): 143–162, 2002), involving more Baer subgeometries contained in the minihyper.     

Quasi exponential decay of a finite difference space discretization of the 1-d wave equation by pointwise interior stabilization

We consider the wave equation on an interval of length 1 with an interior damping at ξ. It is well-known that this system is well-posed in the energy space and that its natural energy is dissipative. Moreover, as it was proved in Ammari et al. (Asymptot Anal 28(3–4):215–240, 2001), the exponential decay property of its solution is equivalent to an observability estimate for the corresponding conservative system. In this case, the observability estimate holds if and only if ξ is a rational number with an irreducible fraction x = \fracpq,\xi=\frac{p}{q}, where p is odd, and therefore under this condition, this system is exponentially stable in the energy space. In this work, we are interested in the finite difference space semi-discretization of the above system. As for other problems (Zuazua, SIAM Rev 47(2):197–243, 2005; Tcheugoué Tébou and Zuazua, Adv Comput Math 26:337–365, 2007), we can expect that the exponential decay of this scheme does not hold in general due to high frequency spurious modes. We first show that this is indeed the case. Secondly we show that a filtering of high frequency modes allows to restore a quasi exponential decay of the discrete energy. This last result is based on a uniform interior observability estimate for filtered solutions of the corresponding conservative semi-discrete system.     

From Constructive Field Theory to Fractional Stochastic Calculus. (I) An introduction: Rough Path Theory and Perturbative Heuristics

Let B = (B ₁(t), . . . , B _d (t)) be a d-dimensional fractional Brownian motion with Hurst index α ≤ 1/4, or more generally a Gaussian process whose paths have the same local regularity. Defining properly iterated integrals of B is a difficult task because of the low H?lder regularity index of its paths. Yet rough path theory shows it is the key to the construction of a stochastic calculus with respect to B, or to solving differential equations driven by B. We intend to show in a forthcoming series of papers how to desingularize iterated integrals by a weak singular non-Gaussian perturbation of the Gaussian measure defined by a limit in law procedure. Convergence is proved by using “standard” tools of constructive field theory, in particular cluster expansions and renormalization. These powerful tools allow optimal estimates of the moments and call for an extension of the Gaussian tools such as for instance the Malliavin calculus. This first paper aims to be both a presentation of the basics of rough path theory to physicists, and of perturbative field theory to probabilists; it is only heuristic, in particular because the desingularization of iterated integrals is really a non-perturbative effect. It is also meant to be a general motivating introduction to the subject, with some insights into quantum field theory and stochastic calculus. The interested reader should read for a second time the companion article (Magnen and Unterberger in From constructive theory to fractional stochastic calculus. (II) The rough path for \frac16 < a < \frac14{\frac{1}{6} < \alpha < \frac{1}{4}}: constructive proof of convergence, 2011, preprint) for the constructive proofs.     

Coarse Differentiation and Multi-flows in Planar Graphs

We show that the multi-commodity max-flow/min-cut gap for series-parallel graphs can be as bad as 2, matching a recent upper bound (Chakrabarti et al. in 49th Annual Symposium on Foundations of Computer Science, pp. 761–770, 2008) for this class, and resolving one side of a conjecture of Gupta, Newman, Rabinovich, and Sinclair. This also improves the largest known gap for planar graphs from \frac32\frac{3}{2} to 2, yielding the first lower bound that does not follow from elementary calculations. Our approach uses the coarse differentiation method of Eskin, Fisher, and Whyte in order to lower bound the distortion for embedding a particular family of shortest-path metrics into L ₁.     

The heat operator and mock Jacobi forms

We study a necessary and sufficient condition for Jacobi integrals of weight -r+\fracj2-r+\frac{j}{2}, r∈ℤ≥0, and index ℳ^(j) on ℋ×ℂ ^j to have a dual Jacobi form of weight r+\fracj2+2r+\frac{j}{2}+2 and index ℳ^(j). Such a meromorphic Jacobi integral with a dual Jacobi form is called a mock Jacobi form whose concept was first introduced by Zagier in Séminaire Bourbaki, 60éme année, 2006–2007, N° 986. In fact, we show the map L^r+1_M^(j)L^{r+1}_{\mathcal{M}^{(j)}} from the space of mock Jacobi forms to that of Jacobi forms is surjective by constructing the corresponding inverse image via Eichler integral of vector valued modular forms which are coming from the theta decomposition of Jacobi forms. We discuss Lerch sums as a typical example.     

Hölder Continuity of Random Processes

For a Young function φ and a Borel probability measure m on a compact metric space (T,d) the minorizing metric is defined by

(1, 1)-<Emphasis Type="Italic">q</Emphasis>-coherent pairs

In this paper, we introduce the concept of (1, 1)-q-coherent pair of linear functionals (U,V)(\mathcal{U},\mathcal{V}) as the q-analogue to the generalized coherent pair studied by Delgado and Marcellán in (Methods Appl Anal 11(2):273–266, 2004). This means that their corresponding sequences of monic orthogonal polynomials {P _n (x)} _n ≥ 0 and {R _n (x)} _n ≥ 0 satisfy

Growth-type invariants for ℤ<Superscript><Emphasis Type="Italic">d</Emphasis></Superscript> subshifts of finite type and arithmetical classes of real numbers

We discuss some numerical invariants of multidimensional shifts of finite type (SFTs) which are associated with the growth rates of the number of admissible finite configurations. Extending an unpublished example of Tsirelson (A strange two-dimensional symbolic system, 1992), we show that growth complexities of the form exp (n ^α+o(1)) are possible for non-integer α’s. In terminology of de Carvalho (Port. Math. 54(1):19–40, 1997), such subshifts have entropy dimension α. The class of possible α’s are identified in terms of arithmetical classes of real numbers of Weihrauch and Zheng (Math. Log. Q. 47(1):51–65, 2001).     

The Projection Median of a Set of Points in ℝ<Superscript><Emphasis Type="Italic">d</Emphasis></Superscript>

The projection median of a finite set of points in ℝ² was introduced by Durocher and Kirkpatrick [Computational Geometry: Theory and Applications, Vol. 42 (5), 364–375, 2009]. They proved that the projection median in ℝ² provides a better approximation of the two-dimensional Euclidean median than the center of mass or the rectilinear median, while maintaining a fixed degree of stability. In this paper we study the projection median of a set of points in ℝ ^d for d≥2. Using results from geometric measure theory we show that the d-dimensional projection median provides a (d/π)B(d/2,1/2)-approximation to the d-dimensional Euclidean median, where B(α,β) denotes the Beta function. We also show that the stability of the d-dimensional projection median is at least \frac1(d/p)B(d/2, 1/2)\frac{1}{(d/\pi)B(d/2, 1/2)}, and its breakdown point is 1/2. Based on the stability bound and the breakdown point, we compare the d-dimensional projection median with the rectilinear median and the center of mass, as a candidate for approximating the d-dimensional Euclidean median. For the special case of d=3, our results imply that the three-dimensional projection median is a (3/2)-approximation of the three-dimensional Euclidean median, which settles a conjecture posed by Durocher.     

A Sharper Estimate on the Betti Numbers of Sets Defined by Quadratic Inequalities

In this paper we consider the problem of bounding the Betti numbers, b _i (S), of a semi-algebraic set S⊂ℝ ^k defined by polynomial inequalities P ₁≥0,…,P _s ≥0, where P _i ∈ℝ[X ₁,…,X _k ], s<k, and deg (P _i )≤2, for 1≤i≤s. We prove that for 0≤i≤k−1,