Growth of permutational extensions

We study the geometry of a class of group extensions, containing permutational wreath products, which we call “permutational extensions”. We construct for all k∈ℕ a torsion group K _k with growth function v_Kk(n) ~ exp(n^1-(1-a)k),       2^3-3/a+2^2-2/a+2^1-1/a=2,v_{K_k}(n)\sim\exp(n^{1-(1-\alpha)^k}),\qquad 2^{3-3/\alpha}+2^{2-2/\alpha}+2^{1-1/\alpha}=2,     

A block coordinate gradient descent method for regularized convex separable optimization and covariance selection

We consider a class of unconstrained nonsmooth convex optimization problems, in which the objective function is the sum of a convex smooth function on an open subset of matrices and a separable convex function on a set of matrices. This problem includes the covariance selection problem that can be expressed as an ℓ ₁-penalized maximum likelihood estimation problem. In this paper, we propose a block coordinate gradient descent method (abbreviated as BCGD) for solving this class of nonsmooth separable problems with the coordinate block chosen by a Gauss-Seidel rule. The method is simple, highly parallelizable, and suited for large-scale problems. We establish global convergence and, under a local Lipschizian error bound assumption, linear rate of convergence for this method. For the covariance selection problem, the method can terminate in O(n³/e){O(n^3/\epsilon)} iterations with an e{\epsilon}-optimal solution. We compare the performance of the BCGD method with the first-order methods proposed by Lu (SIAM J Optim 19:1807–1827, 2009; SIAM J Matrix Anal Appl 31:2000–2016, 2010) for solving the covariance selection problem on randomly generated instances. Our numerical experience suggests that the BCGD method can be efficient for large-scale covariance selection problems with constraints.     

A new asymmetric inclusion region for minimum weight triangulation

As a global optimization problem, planar minimum weight triangulation problem has attracted extensive research attention. In this paper, a new asymmetric graph called one-sided β-skeleton is introduced. We show that the one-sided circle-disconnected (?2b){(\sqrt{2}\beta)} -skeleton is a subgraph of a minimum weight triangulation. An algorithm for identifying subgraph of minimum weight triangulation using the one-sided (?2b){(\sqrt{2}\beta)} -skeleton is proposed and it runs in O(n^4/3+e+min{klogn, n²logn}){O(n^{4/3+\epsilon}+\min\{\kappa \log n, n^2\log n\})} time, where κ is the number of intersected segmented between the complete graph and the greedy triangulation of the point set.     

On some Dirichlet series related to the Riemann zeta function,I

On the assumption of the truth of the Riemann hypothesis for the Riemann zeta function we construct a class of modified von-Mangoldt functions with slightly better mean value properties than the well known function L\Lambda . For every e ? (0,1/2)\varepsilon \in (0,1/2) there is a [(L)\tilde] : \Bbb N ? \Bbb C\tilde {\Lambda} : \Bbb N \to \Bbb C such that¶ i) [(L)\tilde] (n) = L (n) (1 + O(n^-1/4  logn))\tilde {\Lambda} (n) = \Lambda (n) (1 + O(n^{-1/4\,} \log n)) and¶ii) ?_{n \leqq x} [(L)\tilde] (n) (1- [(n)/(x)]) = [(x)/2] + O(x^1/4+e) (x \geqq 2).\sum \limits_{n \leqq x} \tilde {\Lambda} (n) \left(1- {{n}\over{x}}\right) = {{x}\over{2}} + O(x^{1/4+\varepsilon }) (x \geqq 2).¶Unfortunately, this does not lead to an improved error term estimation for the unweighted sum ?_{n \leqq x} [(L)\tilde] (n)\sum \limits_{n \leqq x} \tilde {\Lambda} (n), which would be of importance for the distance between consecutive primes.     

Trigonometric Approximation of SO(N) Loops

This paper extends previous work on approximation of loops to the case of special orthogonal groups SO(N), N≥3. We prove that the best approximation of an SO(N) loop Q(t) belonging to a Hölder class Lip _α , α>1, by a polynomial SO(N) loop of degree ≤n is of order $\mathcal{O}(n^{-\alpha+\epsilon})This paper extends previous work on approximation of loops to the case of special orthogonal groups SO(N), N≥3. We prove that the best approximation of an SO(N) loop Q(t) belonging to a H?lder class Lip _α , α>1, by a polynomial SO(N) loop of degree ≤n is of order O(n^-a+e)\mathcal{O}(n^{-\alpha+\epsilon}) for n≥k, where k=k(Q) is determined by topological properties of the loop and ε>0 is arbitrarily small. The convergence rate is therefore ε-close to the optimal achievable rate of approximation. The construction of polynomial loops involves higher-order splitting methods for the matrix exponential. A novelty in this work is the factorization technique for SO(N) loops which incorporates the loops’ topological aspects.     

Traversing a Set of Points with a Minimum Number of Turns

Given a finite set of points S in ℝ ^d , consider visiting the points in S with a polygonal path which makes a minimum number of turns, or equivalently, has the minimum number of segments (links). We call this minimization problem the minimum link spanning path problem. This natural problem has appeared several times in the literature under different variants. The simplest one is that in which the allowed paths are axis-aligned. Let L(S) be the minimum number of links of an axis-aligned path for S, and let G _n ^d be an n×…×n grid in ℤ ^d . Kranakis et al. (Ars Comb. 38:177–192, 1994) showed that L(G _n ²)=2n−1 and and conjectured that, for all d≥3, We prove the conjecture for d=3 by showing the lower bound for L(G _n ³). For d=4, we prove that For general d, we give new estimates on L(G _n ^d ) that are very close to the conjectured value. The new lower bound of improves previous result by Collins and Moret (Inf. Process. Lett. 68:317–319, 1998), while the new upper bound of differs from the conjectured value only in the lower order terms. For arbitrary point sets, we include an exact bound on the minimum number of links needed in an axis-aligned path traversing any planar n-point set. We obtain similar tight estimates (within 1) in any number of dimensions d. For the general problem of traversing an arbitrary set of points in ℝ ^d with an axis-aligned spanning path having a minimum number of links, we present a constant ratio (depending on the dimension d) approximation algorithm. Work by A. Dumitrescu was partially supported by NSF CAREER grant CCF-0444188. Work by F. Hurtado was partially supported by projects MECMTM2006-01267 and Gen. Cat. 2005SGR00692. Work by P. Valtr was partially supported by the project 1M0545 of the Ministry of Education of the Czech Republic.     

A Volumetric Penrose Inequality for Conformally Flat Manifolds

We consider asymptotically flat Riemannian manifolds with non-negative scalar curvature that are conformal to \mathbbRⁿ\ W, n 3 3{\mathbb{R}^{n}{\setminus} \Omega, n\ge 3}, and so that their boundary is a minimal hypersurface. (Here, W ì \mathbbRⁿ{\Omega\subset \mathbb{R}^{n}} is open bounded with smooth mean-convex boundary.) We prove that the ADM mass of any such manifold is bounded below by \frac12(V/b_n)^(n-2)/n{\frac{1}{2}\left(V/\beta_{n}\right)^{(n-2)/n}}, where V is the Euclidean volume of Ω and β _n is the volume of the Euclidean unit n-ball. This gives a partial proof to a conjecture of Bray and Iga (Commun. Anal. Geom. 10:999–1016, 2002). Surprisingly, we do not require the boundary to be outermost.     

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}}).     

Tilted Edgeworth expansions for asymptotically normal vectors

We obtain the Edgeworth expansion for P(n^1/2([^(q)]-q) < x){P(n^{1/2}(\hat{\theta}-\theta) < x)} and its derivatives, and the tilted Edgeworth (or saddlepoint or small sample) expansion for P([^(q)] < x){P(\hat{\theta} < x)} and its derivatives where [^(q)]{\hat{\theta}} is any vector estimate having the standard cumulant expansions in powers of n^-1{n^{-1}} .     

Additive polylogarithms and their functional equations

Let ${k[\varepsilon]_{2}:=k[\varepsilon]/(\varepsilon^{2})}Let k[e]₂:=k[e]/(e²){k[\varepsilon]_{2}:=k[\varepsilon]/(\varepsilon^{2})} . The single valued real analytic n-polylogarithm L_n: \mathbbC ? \mathbbR{\mathcal{L}_{n}: \mathbb{C} \to \mathbb{R}} is fundamental in the study of weight n motivic cohomology over a field k, of characteristic 0. In this paper, we extend the construction in ünver (Algebra Number Theory 3:1–34, 2009) to define additive n-polylogarithms li_n:k[e]₂? k{li_{n}:k[\varepsilon]_{2}\to k} and prove that they satisfy functional equations analogous to those of L_n{\mathcal{L}_{n}}. Under a mild hypothesis, we show that these functions descend to an analog of the nth Bloch group B_n￠(k[e]₂){B_{n}' (k[\varepsilon]_{2})} defined by Goncharov (Adv Math 114:197–318, 1995). We hope that these functions will be useful in the study of weight n motivic cohomology over k[ε]₂.     

The problem of a minimal ball enclosing <Emphasis Type="Italic">k</Emphasis> points

Under study is the problem of finding a ball of minimal radius enclosing at least k points of a given finite set in a Euclidean space. In the case of a fixed dimension of the space this problem is polynomially solvable, but in general its complexity has not been previously determined. We prove that the problem is NP-hard in the strong sense and obtain a polynomial-time approximation scheme (PTAS) that enables us to solve the problem with an arbitrary relative error ? in time \(O(n^{1/\varepsilon ^2 + 1} d)\), where n is the cardinality of the original set and d is the space dimension.     

Bound states to critical quasilinear Schr?dinger equations

In this paper, we consider the critical quasilinear Schr?dinger equations of the form

Lines, Circles, Planes and Spheres

Let S be a set of n points in ℝ³, no three collinear and not all coplanar. If at most n−k are coplanar and n is sufficiently large, the total number of planes determined is at least 1+k\binomn-k2-\binomk2(\fracn-k2)1+k\binom{n-k}{2}-\binom{k}{2}(\frac{n-k}{2}). For similar conditions and sufficiently large n, (inspired by the work of P.D.T.A. Elliott in Acta Math. Sci. Hung. 18:181–188, 1967) we also show that the number of spheres determined by n points is at least 1+\binomn-13-t₃^orchard(n-1)1+\binom{n-1}{3}-t_{3}^{\mathrm{orchard}}(n-1), and this bound is best possible under its hypothesis. (By t₃^orchard(n)t_{3}^{\mathrm{orchard}}(n), we are denoting the maximum number of three-point lines attainable by a configuration of n points, no four collinear, in the plane, i.e., the classic Orchard Problem.) New lower bounds are also given for both lines and circles.     

On exponential sums over primes in short intervals

Let Λ(n) be the von Mangoldt function, x real and y small compared with x. This paper gives a non-trivial estimate on the exponential sum over primes in short intervals S₂(x,y;a)=?_{x < n ￡ x+y}L(n)e(n² a)S_2(x,y;{\alpha})=\sum_{x < n \le x+y}\Lambda(n)e(n^2 {\alpha}) for all α ∈ [0,1] whenever x^\frac23+e ￡ y ￡ xx^{\frac{2}{3}+{\varepsilon}}\le y \le x . This result is as good as what was previously derived from the Generalized Riemann Hypothesis.     

An algorithmic approach to Ramanujan’s congruences

In this paper we present an algorithm that takes as input a generating function of the form $\prod_{\delta|M}\prod_{n=1}^{\infty}(1-q^{\delta n})^{r_{\delta}}=\sum_{n=0}^{\infty}a(n)q^{n}In this paper we present an algorithm that takes as input a generating function of the form ?_d|M?_n=1^￥(1-q^dn)^r_d=?_n=0^￥a(n)qⁿ\prod_{\delta|M}\prod_{n=1}^{\infty}(1-q^{\delta n})^{r_{\delta}}=\sum_{n=0}^{\infty}a(n)q^{n} and three positive integers m,t,p, and which returns true if a(mn+t) o 0 mod p,n 3 0a(mn+t)\equiv0\pmod{p},n\geq0, or false otherwise. Our method builds on work by Rademacher (Trans. Am. Math. Soc. 51(3):609–636, 1942), Kolberg (Math. Scand. 5:77–92, 1957), Sturm (Lecture Notes in Mathematics, pp. 275–280, Springer, Berlin/Heidelberg, 1987), Eichhorn and Ono (Proceedings for a Conference in Honor of Heini Halberstam, pp. 309–321, 1996).     

Bounds for the cubic Weyl sum

Subject to the abc-conjecture, we improve the standard Weyl estimate for cubic exponential sums in which the argument is a quadratic irrational. Specifically. we show that

On the existence and stability of periodic orbits in non ideal problems: General results

In this work, motivated by non-ideal mechanical systems, we investigate the following O.D.E. [(x)\dot] = f (x) + eg (x, t) + e²[^(g)] (x, t, e){\dot{x} = f (x) + \varepsilon g (x, t) + \varepsilon^{2}\widehat{g} (x, t, \varepsilon)} , where x ? W ì \mathbbRⁿ{x \in \Omega \subset \mathbb{R}^n} , g,[^(g)]{g,\widehat{g}} are T periodic functions of t and there is a ₀ ∈ Ω such that f ( a ₀) = 0 and f ′( a ₀) is a nilpotent matrix. When n = 3 and f (x) = (0, q (x ₃) , 0) we get results on existence and stability of periodic orbits. We apply these results in a non ideal mechanical system: the Centrifugal Vibrator. We make a stability analysis of this dynamical system and get a characterization of the Sommerfeld Effect as a bifurcation of periodic orbits.     

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.     

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.     

Equidistribution of Heegner points and the partition function

Let p(n) denote the number of partitions of a positive integer n. In this paper we study the asymptotic growth of p(n) using the equidistribution of Galois orbits of Heegner points on the modular curve X ₀(6). We obtain a new asymptotic formula for p(n) with an effective error term which is O(n^-(\frac12+d)){O(n^{-(\frac{1}{2}+\delta)})} for some δ > 0. We then use this asymptotic formula to sharpen the classical bounds of Hardy and Ramanujan, Rademacher, and Lehmer on the error term in Rademacher’s exact formula for p(n).