Complex random energy model: zeros and fluctuations

The partition function of the random energy model at inverse temperature $\beta $ is a sum of random exponentials $ \mathcal{Z }_N(\beta )=\sum _{k=1}^N \exp (\beta \sqrt{n} X_k)$ , where $X_1,X_2,\ldots $ are independent real standard normal random variables (=random energies), and $n=\log N$ . We study the large N limit of the partition function viewed as an analytic function of the complex variable $\beta $ . We identify the asymptotic structure of complex zeros of the partition function confirming and extending predictions made in the theoretical physics literature. We prove limit theorems for the random partition function at complex $\beta $ , both on the logarithmic scale and on the level of limiting distributions. Our results cover also the case of the sums of independent identically distributed random exponentials with any given correlations between the real and imaginary parts of the random exponent.     

Online pricing for bundles of multiple items

Given a seller with $k$ types of items, $m$ of each, a sequence of users $\{u_1, u_2,\ldots \}$ arrive one by one. Each user is single-minded, i.e., each user is interested only in a particular bundle of items. The seller must set the price and assign some amount of bundles to each user upon his/her arrival. Bundles can be sold fractionally. Each $u_i$ has his/her value function $v_i(\cdot )$ such that $v_i(x)$ is the highest unit price $u_i$ is willing to pay for $x$ bundles. The objective is to maximize the revenue of the seller by setting the price and amount of bundles for each user. In this paper, we first show that a lower bound of the competitive ratio for this problem is $\Omega (\log h+\log k)$ , where $h$ is the highest unit price to be paid among all users. We then give a deterministic online algorithm, Pricing, whose competitive ratio is $O(\sqrt{k}\cdot \log h\log k)$ . When $k=1$ the lower and upper bounds asymptotically match the optimal result $O(\log h)$ .     

Inequalities for the harmonic numbers

We present various inequalities for the harmonic numbers defined by ${H_n=1+1/2 +\ldots +1/n\,(n\in{\bf N})}$ . One of our results states that we have for all integers n ???2: $$\alpha \, \frac{\log(\log{n}+\gamma)}{n^2} \leq H_n^{1/n} -H_{n+1}^{1/(n+1)} < \beta \, \frac{\log(\log{n}+\gamma)}{n^2}$$ with the best possible constant factors $$\alpha= \frac{6 \sqrt{6}-2 \sqrt[3]{396}}{3 \log(\log{2}+\gamma)}=0.0140\ldots \quad\mbox{and} \quad\beta=1.$$ Here, ?? denotes Euler??s constant.     

Dimension Reduction for Finite Trees in \varvec{\ell _1}

We show that every $n$ -point tree metric admits a $(1+\varepsilon )$ -embedding into $\ell _1^{C(\varepsilon ) \log n}$ , for every $\varepsilon > 0$ , where $C(\varepsilon ) \le O\big ((\frac{1}{\varepsilon })^4 \log \frac{1}{\varepsilon })\big )$ . This matches the natural volume lower bound up to a factor depending only on $\varepsilon $ . Previously, it was unknown whether even complete binary trees on $n$ nodes could be embedded in $\ell _1^{O(\log n)}$ with $O(1)$ distortion. For complete $d$ -ary trees, our construction achieves $C(\varepsilon ) \le O\big (\frac{1}{\varepsilon ^2}\big )$ .     

The growth irregularity of slowly growing entire functions

We show that entire transcendental functions f satisfying $\log M(r,f) = o(\log ^2 r),r \to \infty (M(r,f): = \mathop {\max }\limits_{|z| = r} |f(z)|)$ necessarily have growth irregularity, which increases as the growth diminishes. In particular, if 1 < p < 2, then the asymptotics $\log M(r,f) = \log ^p r + o(\log ^{2 - p} r),r \to \infty ,$ , is impossible. It becomes possible if “o” is replaced by “O.”     

On the Density of the Winding Number of Planar Brownian Motion

We obtain a formula for the density \(f(\theta , t)\) of the winding number of a planar Brownian motion \(Z_t\) around the origin. From this formula, we deduce an expansion for \(f(\log (\sqrt{t})\,\theta ,\,t)\) in inverse powers of \(\log \sqrt{t}\) and \((1+\theta ^2)^{1/2}\) which in particular yields the corrections of any order to Spitzer’s asymptotic law (in Spitzer, Trans. Am. Math. Soc. 87:187–197, 1958). We also obtain an expansion for \(f(\theta ,t)\) in inverse powers of \(\log \sqrt{t}\) , which yields precise asymptotics as \(t \rightarrow \infty \) for a local limit theorem for the windings.     

Strong approximation of empirical process with independent but non-identically distributed random variables

Let{Y_t,t=1,2,…} be independent random variables with continuous distribution functionsF_i(y).For any y,dencte s=F_t(y)=1/t sum from i=1 to t F_i(y).The empirical process is defind by t~(-1/2)R(s,t) whereR(s,t)=t(1/t sum from i=1 to t I_((?)_t(Y_i)≤s)-s)=sum from i=1 to t I_(?)-ts=sum from i=1 to t I_(?)-(?)_t(y)=sum from i=1 to t I_(Y_(?)≤y)-sum from i=1 to t F_i(y).The purpose of this paper is to investigate the asymptotic properties of the empirical processR(s,t).We shall prove that for some integer sequence {t_k},there is a (?)-process (?)(s,t) such that(?)|R(s,t_k)-(?)(s,t_k)|=O(t_k~(1/2)(log t_k)~(-1/4)(log log t_k)~(1/2))a.s.where (?)(s,t) is a two-parameter Gaussian process defined in §1.     

Smoothed performance guarantees for local search

We study popular local search and greedy algorithms for standard machine scheduling problems. The performance guarantee of these algorithms is well understood, but the worst-case lower bounds seem somewhat contrived and it is questionable whether they arise in practical applications. To find out how robust these bounds are, we study the algorithms in the framework of smoothed analysis, in which instances are subject to some degree of random noise. While the lower bounds for all scheduling variants with restricted machines are rather robust, we find out that the bounds are fragile for unrestricted machines. In particular, we show that the smoothed performance guarantee of the jump and the lex-jump algorithm are (in contrast to the worst case) independent of the number of machines. They are  \(\Theta (\phi )\) and  \(\Theta (\log \phi )\) , respectively, where  \(1/\phi \) is a parameter measuring the magnitude of the perturbation. The latter immediately implies that also the smoothed price of anarchy is  \(\Theta (\log \phi )\) for routing games on parallel links. Additionally, we show that for unrestricted machines also the greedy list scheduling algorithm has an approximation guarantee of   \(\Theta (\log \phi )\) .     

On Shintani’s ray class invariant for totally real number fields

We introduce a ray class invariant ${X(\mathfrak{C})}$ for a totally real field, following Shintani’s work in the real quadratic case. We prove a factorization formula ${X(\mathfrak{C})=X_1(\mathfrak{C})\cdots X_n(\mathfrak{C})}$ where each ${X_i(\mathfrak{C})}$ corresponds to a real place. Although this factorization depends a priori on some choices (especially on a cone decomposition), we can show that it is actually independent of these choices. Finally, we describe the behavior of ${X_i(\mathfrak{C})}$ when the signature of ${\mathfrak{C}}$ at a real place is changed. This last result is also interpreted in terms of the derivatives L′(0, χ) of the L-functions and certain Stark units.     

A sharp lower bound for the log canonical threshold

In this note, we prove a sharp lower bound for the log canonical threshold of a plurisubharmonic function ${\varphi}$ with an isolated singularity at 0 in an open subset of ${\mathbb{C}^n}$ . This threshold is defined as the supremum of constants c > 0 such that ${e^{-2c\varphi}}$ is integrable on a neighborhood of 0. We relate ${c(\varphi)}$ to the intermediate multiplicity numbers ${e_j(\varphi)}$ , defined as the Lelong numbers of ${(dd^c\varphi)^j}$ at 0 (so that in particular ${e_0(\varphi)=1}$ ). Our main result is that ${c(\varphi)\geqslant\sum_{j=0}^{n-1} e_j(\varphi)/e_{j+1}(\varphi)}$ . This inequality is shown to be sharp; it simultaneously improves the classical result ${c(\varphi)\geqslant 1/e_1(\varphi)}$ due to Skoda, as well as the lower estimate ${c(\varphi)\geqslant n/e_n(\varphi)^{1/n}}$ which has received crucial applications to birational geometry in recent years. The proof consists in a reduction to the toric case, i.e. singularities arising from monomial ideals.     

Pointwise convergence in Pringsheim’s sense of the summability of Fourier transforms on Wiener amalgam spaces

New multi-dimensional Wiener amalgam spaces \(W_c(L_p,\ell _\infty )(\mathbb{R }^d)\) are introduced by taking the usual one-dimensional spaces coordinatewise in each dimension. The strong Hardy-Littlewood maximal function is investigated on these spaces. The pointwise convergence in Pringsheim’s sense of the \(\theta \) -summability of multi-dimensional Fourier transforms is studied. It is proved that if the Fourier transform of \(\theta \) is in a suitable Herz space, then the \(\theta \) -means \(\sigma _T^\theta f\) converge to \(f\) a.e. for all \(f\in W_c(L_1(\log L)^{d-1},\ell _\infty )(\mathbb{R }^d)\) . Note that \(W_c(L_1(\log L)^{d-1},\ell _\infty )(\mathbb{R }^d) \supset W_c(L_r,\ell _\infty )(\mathbb{R }^d) \supset L_r(\mathbb{R }^d)\) and \(W_c(L_1(\log L)^{d-1},\ell _\infty )(\mathbb{R }^d) \supset L_1(\log L)^{d-1}(\mathbb{R }^d)\) , where \(1 . Moreover, \(\sigma _T^\theta f(x)\) converges to \(f(x)\) at each Lebesgue point of \(f\in W_c(L_1(\log L)^{d-1},\ell _\infty )(\mathbb{R }^d)\) .     

On Sub-determinants and the Diameter of Polyhedra

We derive a new upper bound on the diameter of a polyhedron \(P = \{x {\in } {\mathbb {R}}^n :Ax\le b\}\) , where \(A \in {\mathbb {Z}}^{m\times n}\) . The bound is polynomial in \(n\) and the largest absolute value of a sub-determinant of \(A\) , denoted by \(\Delta \) . More precisely, we show that the diameter of \(P\) is bounded by \(O(\Delta ^2 n^4\log n\Delta )\) . If \(P\) is bounded, then we show that the diameter of \(P\) is at most \(O(\Delta ^2 n^{3.5}\log n\Delta )\) . For the special case in which \(A\) is a totally unimodular matrix, the bounds are \(O(n^4\log n)\) and \(O(n^{3.5}\log n)\) respectively. This improves over the previous best bound of \(O(m^{16}n^3(\log mn)^3)\) due to Dyer and Frieze (Math Program 64:1–16, 1994).     

Averaged Pointwise Bounds for Deformations of Schrödinger Eigenfunctions

Let (M,g) be an n-dimensional, compact Riemannian manifold and ${P_0(\hbar) = -\hbar{^2} \Delta_g + V(x)}$ be a semiclassical Schrödinger operator with ${\hbar \in (0,\hbar_0]}$ . Let ${E(\hbar) \in [E-o(1),E+o(1)]}$ and ${(\phi_{\hbar})_{\hbar \in (0,\hbar_0]}}$ be a family of L ²-normalized eigenfunctions of ${P_0(\hbar)}$ with ${P_0(\hbar) \phi_{\hbar} = E(\hbar) \phi_{\hbar}}$ . We consider magnetic deformations of ${P_0(\hbar)}$ of the form ${P_u(\hbar) = - \Delta_{\omega_u}(\hbar) + V(x)}$ , where ${\Delta_{\omega_u}(\hbar) = (\hbar d + i \omega_u(x))^*({\hbar}d + i \omega_u(x))}$ . Here, u is a k-dimensional parameter running over ${B^k(\epsilon)}$ (the ball of radius ${\epsilon}$ ), and the family of the magnetic potentials ${(w_u)_{u\in B^k(\epsilon)}}$ satisfies the admissibility condition given in Definition 1.1. This condition implies that k ≥ n and is generic under this assumption. Consider the corresponding family of deformations of ${(\phi_{\hbar})_{\hbar \in (0, \hbar_0]}}$ , given by ${(\phi^u_{\hbar})_{\hbar \in(0, \hbar_0]}}$ , where $$\phi_{\hbar}^{(u)}:= {\rm e}^{-it_0 P_u(\hbar)/\hbar}\phi_{\hbar}$$ for ${|t_0|\in (0,\epsilon)}$ ; the latter functions are themselves eigenfunctions of the ${\hbar}$ -elliptic operators ${Q_u(\hbar): ={\rm e}^{-it_0P_u(\hbar)/\hbar} P_0(\hbar) {\rm e}^{it_0 P_u(\hbar)/\hbar}}$ with eigenvalue ${E(\hbar)}$ and ${Q_0(\hbar) = P_{0}(\hbar)}$ . Our main result, Theorem1.2, states that for ${\epsilon >0 }$ small, there are constants ${C_j=C_j(M,V,\omega,\epsilon) > 0}$ with j = 1,2 such that $$C_{1}\leq \int\limits_{\mathcal{B}^k(\epsilon)} |\phi_{\hbar}^{(u)}(x)|^2 \, {\rm d}u \leq C_{2}$$ , uniformly for ${x \in M}$ and ${\hbar \in (0,h_0]}$ . We also give an application to eigenfunction restriction bounds in Theorem 1.3.     

{\mathcal{C}^{\alpha}}-regularity for a class of non-diagonal elliptic systems with p-growth

We consider weak solutions to nonlinear elliptic systems in a W ^1,p -setting which arise as Euler equations to certain variational problems. The solutions are assumed to be stationary in the sense that the differential of the variational integral vanishes with respect to variations of the dependent and independent variables. We impose new structure conditions on the coefficients which yield everywhere ${\mathcal{C}^{\alpha}}$ -regularity and global ${\mathcal{C}^{\alpha}}$ -estimates for the solutions. These structure conditions cover variational integrals like ${\int F(\nabla u)\; dx}$ with potential ${F(\nabla u):=\tilde F (Q_1(\nabla u),\ldots, Q_N(\nabla u))}$ and positively definite quadratic forms in ${\nabla u}$ defined as ${Q_i(\nabla u)=\sum_{\alpha \beta} a_i^{\alpha \beta} \nabla u^\alpha \cdot \nabla u^\beta}$ . A simple example consists in ${\tilde F(\xi_1,\xi_2):= |\xi_1|^{\frac{p}{2}} + |\xi_2|^{\frac{p}{2}}}$ or ${\tilde F(\xi_1,\xi_2):= |\xi_1|^{\frac{p}{4}}|\xi_2|^{\frac{p}{4}}}$ . Since the Q _i need not to be linearly dependent our result covers a class of nondiagonal, possibly nonmonotone elliptic systems. The proof uses a new weighted norm technique with singular weights in an L ^p -setting.     

Boundedness and Compactness of Pseudodifferential Operators with Non-Regular Symbols on Weighted Lebesgue Spaces

Applying the boundedness on weighted Lebesgue spaces of the maximal singular integral operator S _* related to the Carleson?CHunt theorem on almost everywhere convergence, we study the boundedness and compactness of pseudodifferential operators a(x, D) with non-regular symbols in ${L^\infty(\mathbb{R}, V(\mathbb{R})), PC(\overline{\mathbb{R}}, V(\mathbb{R}))}$ and ${\Lambda_\gamma(\mathbb{R}, V_d(\mathbb{R}))}$ on the weighted Lebesgue spaces ${L^p(\mathbb{R},w)}$ , with 1?< p <? ?? and ${w\in A_p(\mathbb{R})}$ . The Banach algebras ${L^\infty(\mathbb{R}, V(\mathbb{R}))}$ and ${PC(\overline{\mathbb{R}}, V(\mathbb{R}))}$ consist, respectively, of all bounded measurable or piecewise continuous ${V(\mathbb{R})}$ -valued functions on ${\mathbb{R}}$ where ${V(\mathbb{R})}$ is the Banach algebra of all functions on ${\mathbb{R}}$ of bounded total variation, and the Banach algebra ${\Lambda_\gamma(\mathbb{R}, V_d(\mathbb{R}))}$ consists of all Lipschitz ${V_d(\mathbb{R})}$ -valued functions of exponent ${\gamma \in (0,1]}$ on ${\mathbb{R}}$ where ${V_d(\mathbb{R})}$ is the Banach algebra of all functions on ${\mathbb{R}}$ of bounded variation on dyadic shells. Finally, for the Banach algebra ${\mathfrak{A}_{p,w}}$ generated by all pseudodifferential operators a(x, D) with symbols ${a(x, \lambda) \in PC(\overline{\mathbb{R}}, V(\mathbb{R}))}$ on the space ${L^p(\mathbb{R}, w)}$ , we construct a non-commutative Fredholm symbol calculus and give a Fredholm criterion for the operators ${A \in \mathfrak{A}_{p,w}}$ .     

Nielsen coincidence,fixed point and root theories of n-valued maps

Let ${(\phi, \psi)}$ be an (m, n)-valued pair of maps ${\phi, \psi : X \multimap Y}$ , where ${\phi}$ is an m-valued map and ${\psi}$ is n-valued, on connected finite polyhedra. A point ${x \in X}$ is a coincidence point of ${\phi}$ and ${\psi}$ if ${\phi(x) \cap \psi(x) \neq \emptyset}$ . We define a Nielsen coincidence number ${N(\phi : \psi)}$ which is a lower bound for the number of coincidence points of all (m, n)-valued pairs of maps homotopic to ${(\phi, \psi)}$ . We calculate ${N(\phi : \psi)}$ for all (m, n)-valued pairs of maps of the circle and show that ${N(\phi : \psi)}$ is a sharp lower bound in that setting. Specifically, if ${\phi}$ is of degree a and ${\psi}$ of degree b, then ${N(\phi : \psi) = \frac{|an - bm|}{\langle m, n \rangle}}$ , where ${\langle m, n \rangle}$ is the greatest common divisor of m and n. In order to carry out the calculation, we obtain results, of independent interest, for n-valued maps of compact connected Lie groups that relate the Nielsen fixed point number of Helga Schirmer to the Nielsen root number of Michael Brown.     

The Duffin–Schaeffer conjecture with extra divergence II

In 2012 the authors set out a programme to prove the Duffin–Schaeffer conjecture for measures arbitrarily close to Lebesgue measure. In this paper we take a new step in this direction. Given a non-negative function $\psi : \mathbb N \rightarrow \mathbb R $ , let $W(\psi )$ denote the set of real numbers $x$ such that $|nx -a| < \psi (n) $ for infinitely many reduced rationals $a/n \ (n>0) $ . Our main result is that $W(\psi )$ is of full Lebesgue measure if there exists a $c > 0 $ such that $$\begin{aligned} \sum _{n\ge 16} \, \frac{\varphi (n) \psi (n)}{n \exp (c(\log \log n)(\log \log \log n))} \, = \, \infty \, . \end{aligned}$$      

Strongly embedded subspaces of p-convex Banach function spaces

Let $X(\mu )$ be a p-convex ( $1\le p<\infty $ ) order continuous Banach function space over a positive finite measure  $\mu $ . We characterize the subspaces of  $X(\mu )$ which can be found simultaneously in  $X(\mu )$ and a suitable $L^1(\eta )$ space, where $\eta $ is a positive finite measure related to the representation of  $X(\mu )$ as an $L^p(m)$ space of a vector measure  $m$ . We provide in this way new tools to analyze the strict singularity of the inclusion of  $X(\mu )$ in such an $L^1$ space. No rearrangement invariant type restrictions on  $X(\mu )$ are required.     

Generalized \mathcal{C}-concave conditions and their applications

We first introduce two general $\mathcal{C}$ -concave conditions, and show the implications between $\mathcal{C}$ -concave, diagonally $\mathcal{C}$ -concave, diagonally $\mathcal{C}$ -quasiconcave, and ??-diagonally $\mathcal{C}$ -quasiconcave conditions which generalize both concavity and quasiconcavity simultaneously without assuming the linear structure. Using the ??-diagonal $\mathcal{C}$ -quasiconcavity, we prove two non-compact minimax inequalities in a topological space which generalize Fan??s minimax inequality and its generalizations in several aspects. As applications, we will prove a general minimax theorem and basic geometric formulations of the minimax inequality in a topological space.