text:
# Mathematics (math)

• This paper considers the problem of solving systems of quadratic equations, namely, recovering an object of interest $\mathbf{x}^{\natural}\in\mathbb{R}^{n}$ from $m$ quadratic equations/samples $y_{i}=(\mathbf{a}_{i}^{\top}\mathbf{x}^{\natural})^{2}$, $1\leq i\leq m$. This problem, also dubbed as phase retrieval, spans multiple domains including physical sciences and machine learning. We investigate the efficiency of gradient descent (or Wirtinger flow) designed for the nonconvex least squares problem. We prove that under Gaussian designs, gradient descent --- when randomly initialized --- yields an $\epsilon$-accurate solution in $O\big(\log n+\log(1/\epsilon)\big)$ iterations given nearly minimal samples, thus achieving near-optimal computational and sample complexities at once. This provides the first global convergence guarantee concerning vanilla gradient descent for phase retrieval, without the need of (i) carefully-designed initialization, (ii) sample splitting, or (iii) sophisticated saddle-point escaping schemes. All of these are achieved by exploiting the statistical models in analyzing optimization algorithms, via a leave-one-out approach that enables the decoupling of certain statistical dependency between the gradient descent iterates and the data.
• Mar 22 2018 math.CO arXiv:1803.07694v1
Consider the following two ways to colour the vertices of a graph where the requirement that adjacent vertices get distinct colours is relaxed. A colouring has "defect" $d$ if each monochromatic component has maximum degree at most $d$. A colouring has "clustering" $c$ if each monochromatic component has at most $c$ vertices. This paper surveys research on these types of colourings, where the first priority is to minimise the number of colours, with small defect or small clustering as a secondary goal. List colouring variants are also considered. The following graph classes are studied: outerplanar graphs, planar graphs, graphs embeddable in surfaces, graphs with given maximum degree, graphs with given maximum average degree, graphs excluding a given subgraph, graphs with linear crossing number, linklessly or knotlessly embeddable graphs, graphs with given Colin de Verdière parameter, graphs with given circumference, graphs excluding a fixed graph as an immersion, graphs with given thickness, graphs with given stack- or queue-number, graphs excluding $K_t$ as a minor, graphs excluding $K_{s,t}$ as a minor, and graphs excluding an arbitrary graph $H$ as a minor. Several open problems are discussed.
• This paper considers the word problem for free inverse monoids of finite rank from a language theory perspective. It is shown that no free inverse monoid has context-free word problem; that the word problem of the free inverse monoid of rank $1$ is both $2$-context-free (an intersection of two context-free languages) and ET0L; that the co-word problem of the free inverse monoid of rank $1$ is context-free; and that the word problem of a free inverse monoid of rank greater than $1$ is not poly-context-free.
• We study the Wasserstein metric $W_p$, a notion of distance between two probability distributions, from the perspective of Fourier Analysis and discuss applications. In particular, we bound the Earth Mover Distance $W_1$ between the distribution of quadratic residues in a finite field $\mathbb{F}_p$ and uniform distribution by $\lesssim p^{-1/2}$ (the Polya-Vinogradov inequality implies $\lesssim p^{-1/2} \log{p}$). We also show for continuous $f:\mathbb{T} \rightarrow \mathbb{R}_{}$ with mean value 0 $$(\mboxnumber of roots of~f) ⋅\left( \sum_k=1^∞ \frac |\widehatf(k)|^2k^2\right)^\frac12 ≳\frac\|f\|^2_L^1(\mathbbT)\|f\|_L^∞(\mathbbT).$$ Moreover, we show that for a Laplacian eigenfunction $-\Delta_g \phi_{\lambda} = \lambda \phi_{\lambda}$ on a compact Riemannian manifold $W_p\left(\max\left\{\phi_{\lambda}, 0\right\}dx, \max\left\{-\phi_{\lambda}, 0\right\} dx\right) \lesssim_p \sqrt{\log{\lambda}/\lambda} \|\phi_{\lambda}\|_{L^1}^{1/p}$ which is at most a factor $\sqrt{\log{\lambda}}$ away from sharp. Several other problems are discussed.
• We interpret part of the experimental results of Shwartz-Ziv and Tishby [2017]. Inspired by these results, we established a conjecture of the dynamics of the machinary of deep neural network. This conjecture can be used to explain the counterpart result by Saxe et al. [2018].
• In empirical risk optimization, it has been observed that stochastic gradient implementations that rely on random reshuffling of the data achieve better performance than implementations that rely on sampling the data uniformly. Recent works have pursued justifications for this behavior by examining the convergence rate of the learning process under diminishing step-sizes. This work focuses on the constant step-size case. In this case, convergence is guaranteed to a small neighborhood of the optimizer albeit at a linear rate. The analysis establishes analytically that random reshuffling outperforms uniform sampling by showing explicitly that iterates approach a smaller neighborhood of size $O(\mu^2)$ around the minimizer rather than $O(\mu)$. Furthermore, we derive an analytical expression for the steady-state mean-square-error performance of the algorithm, which helps clarify in greater detail the differences between sampling with and without replacement. We also explain the periodic behavior that is observed in random reshuffling implementations.
• Applications in machine learning, optimization, and control require the sequential selection of a few system elements, such as sensors, data, or actuators, to optimize the system performance across multiple time steps. However, in failure-prone and adversarial environments, sensors get attacked, data get deleted, and actuators fail. Thence, traditional sequential design paradigms become insufficient and, in contrast, resilient sequential designs that adapt against system-wide attacks, deletions, or failures become important. In general, resilient sequential design problems are computationally hard. Also, even though they often involve objective functions that are monotone and (possibly) submodular, no scalable approximation algorithms are known for their solution. In this paper, we provide the first scalable algorithm, that achieves the following characteristics: system-wide resiliency, i.e., the algorithm is valid for any number of denial-of-service attacks, deletions, or failures; adaptiveness, i.e., at each time step, the algorithm selects system elements based on the history of inflicted attacks, deletions, or failures; and provable approximation performance, i.e., the algorithm guarantees for monotone objective functions a solution close to the optimal. We quantify the algorithm's approximation performance using a notion of curvature for monotone (not necessarily submodular) set functions. Finally, we support our theoretical analyses with simulated experiments, by considering a control-aware sensor scheduling scenario, namely, sensing-constrained robot navigation.
• Mar 22 2018 cs.IT math.IT arXiv:1803.07937v1
The existence of a unique Augustin mean is established for any positive order and probability mass function on the input set. The Augustin mean is shown to be the unique fixed point of an operator defined in terms of the order and the input distribution. The Augustin information is shown to be continuously differentiable in the order. For any channel and any convex constraint set with finite Augustin capacity, the existence of a unique Augustin center and associated van Erven-Harremoes bound are established.The Augustin-Legendre (A-L) information, capacity, center, and radius are introduced and the latter three is proved to be equal to the corresponding Renyi-Gallager quantities. The equality of the A-L capacity to the A-L radius for arbitrary channels and the existence of a unique A-L center for channels with finite A-L capacity are established. For all interior points of the feasible set of cost constraints, the cost constrained Augustin capacity and center are expressed in terms the A-L capacity and center. Certain shift invariant families of probability measures and certain Gaussian channels are analyzed as examples.
• Given a complex manifold endowed with a $\mathbb{C}^\times$-action and a DQ-algebra equipped with a compatible holomorphic Frobenius action (F-action), we prove that if the $\mathbb{C}^\times$-action is free and proper, then the category of F-equivariant DQ-modules is equivalent to the category of modules over the sheaf of invariant sections of the DQ-algebra. As an application, we deduce the codimension three conjecture for formal microdifferential modules from the one for DQ-modules on a symplectic manifold.
• We study the stabilization issue of the Benjamin-Bona-Mahony (BBM) equation on a finite star-shaped network with a damping term acting on the central node. In a first time, we prove the well-posedness of this system. Then thanks to the frequency domain method, we get the asymptotic stabilization result.
• In this paper we prove an $n$th root test for series as well as a Cauchy-Hadamard type formula and Abel's' theorem for power series on universally complete Archimedean complex vector lattices. These results are aimed at developing an alternative approach to the classical theory of complex series and power series using the topology of order convergence.
• Mar 22 2018 math.OC arXiv:1803.07872v1
We study a differential game where two players separately control their own dynamics, pay a running cost, and moreover pay an exit cost (quitting the game) when they leave a fixed domain. In particular, each player has its own domain and the exit cost consists of three different exit costs, depending whether either the first player only leaves its domain, or the second player only leaves its domain, or they both simultaneously leave their own domain. We prove that, under suitable hypotheses, the lower and upper value are continuous and are, respectively, the unique viscosity solution of a suitable Dirichlet problem for a Hamilton-Jacobi-Isaacs equation. The continuity of the values relies on the existence of suitable non-anticipative strategies respecting the domain-constraint. This problem is also treated in this work.
• Mar 22 2018 math.CV arXiv:1803.07862v1
We generalize the notion of tame discrete sets introduced by Rosay and Rudin from complex-Euclidean space to arbitrary complex manifolds and establish their basic properties. We show that complex-linear algebraic groups different from the complex line or the punctured complex line contain tame discrete sets.
• In this paper, we describe a new Niederreiter cryptosystem based on quasi-cyclic $\frac{m-1}{m}$ codes that is quantum-secure. This new cryptosystem has good transmission rate compared to the one using binary Goppa codes and uses smaller keys.
• In this paper, we study the problem of distributed multi-agent optimization over a network, where each agent possesses a local cost function that is smooth and strongly convex. The global objective is to find a common solution that minimizes the average of all cost functions. Assuming agents only have access to unbiased estimates of the gradients of their local cost functions, we consider a distributed stochastic gradient tracking method. We show that, in expectation, the iterates generated by each agent are attracted to a neighborhood of the optimal solution, where they accumulate exponentially fast (under a constant step size choice). More importantly, the limiting (expected) error bounds on the distance of the iterates from the optimal solution decrease with the network size, which is a comparable performance to a centralized stochastic gradient algorithm. Numerical examples further demonstrate the effectiveness of the method.
• We prove that unless P=NP, there exists no polynomial time (or even pseudo-polynomial time) algorithm that can test whether the optimal value of a nonlinear optimization problem where the objective and constraints are given by low-degree polynomials is attained. If the degrees of these polynomials are fixed, our results along with previously-known "Frank-Wolfe type" theorems imply that exactly one of two cases can occur: either the optimal value is attained on every instance, or it is strongly NP-hard to distinguish attainment from non-attainment. We also show that testing for some well-known sufficient conditions for attainment of the optimal value, such as coercivity of the objective function and closedness and boundedness of the feasible set, is strongly NP-hard. As a byproduct, our proofs imply that testing the Archimedean property of a quadratic module is strongly NP-hard, a property that is of independent interest to the convergence of the Lasserre hierarchy. Finally, we give semidefinite programming (SDP)-based sufficient conditions for attainment of the optimal value, in particular a new characterization of coercive polynomials that lends itself to an SDP hierarchy.
• Mar 22 2018 math.ST stat.TH arXiv:1803.07645v1
Smoothing splines can be thought of as the posterior mean of a Gaussian process regression in a certain limit. By constructing a reproducing kernel Hilbert space with an appropriate inner product, the Bayesian form of the V-spline is derived when the penalty term is a fixed constant instead of a function. An extension to the usual generalized cross-validation formula is utilized to find the optimal V-spline parameters.
• We present criteria for establishing a triangulation of a manifold. Given a manifold M, a simplicial complex A, and a map H from the underlying space of A to M, our criteria are presented in local coordinate charts for M, and ensure that H is a homeomorphism. These criteria do not require a differentiable structure, or even an explicit metric on M. No Delaunay property of A is assumed. The result provides a triangulation guarantee for algorithms that construct a simplicial complex by working in local coordinate patches. Because the criteria are easily verified in such a setting, they are expected to be of general use.
• We uncover a fairly general principle in online learning: If regret can be (approximately) expressed as a function of certain "sufficient statistics" for the data sequence, then there exists a special Burkholder function that 1) can be used algorithmically to achieve the regret bound and 2) only depends on these sufficient statistics, not the entire data sequence, so that the online strategy is only required to keep the sufficient statistics in memory. This characterization is achieved by bringing the full power of the Burkholder Method --- originally developed for certifying probabilistic martingale inequalities --- to bear on the online learning setting. To demonstrate the scope and effectiveness of the Burkholder method, we develop a novel online strategy for matrix prediction that attains a regret bound corresponding to the variance term in matrix concentration inequalities. We also present a linear-time/space prediction strategy for parameter free supervised learning with linear classes and general smooth norms.
• Mar 22 2018 math.AG arXiv:1803.07596v1
We define the notion of Mumford divisors, argue that they are the natural divisors to study on reduced but non-normal varieties and prove a structure theorem for the Mumford class group.
• In this paper, we focus on solving a distributed convex optimization problem in a network, where each agent has its own convex cost function and the goal is to minimize the sum of the agents' cost functions while obeying the network connectivity structure. In order to minimize the sum of the cost functions, we consider a new distributed gradient-based method where each node maintains two estimates, namely, an estimate of the optimal decision variable and an estimate of the gradient for the average of the agents' objective functions. From the viewpoint of an agent, the information about the decision variable is pushed to the neighbors, while the information about the gradients is pulled from the neighbors (hence giving the name "push-pull gradient method"). The method unifies the algorithms with different types of distributed architecture, including decentralized (peer-to-peer), centralized (master-slave), and semi-centralized (leader-follower) architecture. We show that the algorithm converges linearly for strongly convex and smooth objective functions over a directed static network. In our numerical test, the algorithm performs well even for time-varying directed networks.
• The PWP map was introduced by the second author as a tool for ranking nodes in networks. In this work we extend this technique so that it can be used to rank links as well. Applying the Girvan-Newman algorithm a ranking method on links induces a deconstruction method for networks, therefore we obtain new methods for finding clustering and core-periphery structures on networks.
• We prove improved bounds on how localized an eigenvector of a high girth regular graph can be, and present examples showing that these bounds are close to sharp. This study was initiated by Brooks and Lindenstrauss (2009) who relied on the observation that certain suitably normalized averaging operators on high girth graphs are hyper-contractive and can be used to approximate projectors onto the eigenspaces of such graphs. Informally, their delocalization result in the contrapositive states that for any $\varepsilon \in (0,1)$ and positive integer $k,$ if a $(d+1)-$regular graph has an eigenvector which supports $\varepsilon$ fraction of the $\ell_2^2$ mass on a subset of $k$ vertices, then the graph must have a cycle of size $\tilde{O}(\log_{d}(k)/\varepsilon^2)$, suppressing logarithmic terms in $1/\varepsilon$. In this paper, we improve the upper bound to $\tilde{O}(\log_{d}(k)/\varepsilon)$ and present a construction showing a lower bound of $\Omega(\log_d(k)/\varepsilon)$. Our construction is probabilistic and involves gluing together a pair of trees while maintaining high girth as well as control on the eigenvectors and could be of independent interest.
• We study locally compact groups having all subgroups minimal. We call such groups hereditarily minimal. In 1972 Prodanov proved that the infinite hereditarily minimal compact abelian groups are precisely the groups $\mathbb Z_p$ of $p$-adic integers. We extend Prodanov's theorem to the non-abelian case at several levels. For infinite hypercentral (in particular, nilpotent) locally compact groups we show that the hereditarily minimal ones remain the same as in the abelian case. On the other hand, we classify completely the locally compact solvable hereditarily minimal groups, showing that in particular they are always compact and metabelian. The proofs involve the (hereditarily) locally minimal groups, introduced similarly. In particular, we prove a conjecture by He, Xiao and the first two authors, showing that the group $\mathbb Q_p\rtimes \mathbb Q_p^*$ is hereditarily locally minimal, where $\mathbb Q_p^*$ is the multiplicative group of non-zero $p$-adic numbers acting on the first component by multiplication. Furthermore, it turns out that the locally compact solvable hereditarily minimal groups are closely related to this group.
• Mar 22 2018 math.DS arXiv:1803.08032v1
Let $\{N_t\}$ be a holomorphic family of degree $d\ge 3$ Newton maps. By studying the related Berkovich dynamics, we obtain an estimate of the weak limit of the maximal measures of $N_t$. Moreover, we give a complete description of the rescaling limits for $\{N_t\}$.
• The goal of this paper is to study a distributed version of the gradient temporal-difference (GTD) learning algorithm for multi-agent Markov decision processes (MDPs). The temporal difference (TD) learning is a reinforcement learning (RL) algorithm which learns an infinite horizon discounted cost function (or value function) for a given fixed policy without the model knowledge. In the distributed RL case each agent receives local reward through a local processing. Information exchange over sparse communication network allows the agents to learn the global value function corresponding to a global reward, which is a sum of local rewards. In this paper, the problem is converted into a constrained convex optimization problem with a consensus constraint. Then, we propose a primal-dual distributed GTD algorithm and prove that it almost surely converges to a set of stationary points of the optimization problem.
• We use recent results of Rolen, Zwegers, and the first author to study characters of irreducible (highest weight) modules for the vertex operator algebra $L_{\frak{sl}_\ell}(-\Lambda_0)$. We establish asymptotic behaviors of characters for the (ordinary) irreducible $L_{\frak{sl}_\ell}(-\Lambda_0)$-modules. As a consequence we prove that their quantum dimensions are one, as predicted by representation theory. We also establish a full asymptotic expansion of irreducible characters for $\frak{sl}_3$. Finally, we determine a decomposition formula for the full characters in terms of unary theta and false theta functions which allows us to study their modular properties.
• We define some signature invariants for a class of knotted trivalent graphs using branched covers. We relate them to classical signatures of knots and links. Finally, we explain how to compute these invariants through the example of Kinoshita's knotted theta graph.
• We give a brief re-exposition of the theory due to Pauli and Sinclair of ramification polygons of Eisenstein polynomials over p-adic fields, their associated residual polynomials and an algorithm to produce all extensions for a given ramification polygon. We supplement this with an algorithm to produce all ramification polygons of a given degree, and hence we can produce all totally ramified extensions of a given degree.
• We study a system of nonlinear partial differential equations describing the unsteady motions of incompressible chemically reacting non-Newtonian fluids. The system under consideration consists of the generalized Navier-Stokes equations with a power-law type stress-strain relation, where the power-law index depends on the concentration of a chemical, coupled to a convection-diffusion equation for the concentration. This system of equations arises in the rheology of the synovial fluid found in the cavities of synovial joints. We prove the existence of global weak solutions of the non-stationary model by using the Galerkin method combined with generalized monotone operator theory and parabolic De Giorgi-Nash-Moser theory. As the governing equations involve a nonlinearity with a variable power-law index, our proofs exploit the framework of generalized Sobolev spaces with variable integrability exponent.
• We give a notion of quantum automorphism group of graph C*-algebras without sink at critical inverse temperature. This is defined to be the universal object of a category of CQG's having a linear action in the sense of [11] and preserving the KMS state at critical inverse temperature. We show that this category for a certain KMS state at critical inverse temperature coincides with the category introduced in [11] for a class of graphs. We also introduce an orthogonal filtration on Cuntz algebra with respect to the unique KMS state and show that the category of CQG's preserving the orthogonal filtration coincides with the category introduced in this paper.
• In 2008, Kauffman and Lomonaco introduce the concepts of a knot mosaic and the mosaic number of a knot or link, the smallest integer $n$ such that a knot or link can be represented on an $n$-mosaic. In arXiv:1702.06462, the authors explore space-efficient knot mosaics and the tile number of a knot or link, the smallest number of non-blank tiles necessary to depict the knot or link on a mosaic. They determine bounds for the tile number in terms of the mosaic number. In this paper, we focus specifically on prime knots with mosaic number 6. We determine a complete list of these knots, provide a minimal, space-efficient knot mosaic for each of them, and determine the tile number (or minimal mosaic tile number) of each of them.
• Let $k({\bf x})=k(x_1,\ldots ,x_n)$ be the rational function field, and $k\subsetneqq L\subsetneqq k({\bf x})$ an intermediate field. Then, Hilbert's fourteenth problem asks whether the $k$-algebra $A:=L\cap k[x_1,\ldots ,x_n]$ is finitely generated. Various counterexamples to this problem were already given, but the case $[k({\bf x}):L]=2$ was open when $n=3$. In this paper, we study the problem in terms of the field-theoretic properties of $L$. We say that $L$ is minimal if the transcendence degree $r$ of $L$ over $k$ is equal to that of $A$. We show that, if $r\ge 2$ and $L$ is minimal, then there exists $\sigma \in {\mathop{\rm Aut}\nolimits}_kk(x_1,\ldots ,x_{n+1})$ for which $\sigma (L(x_{n+1}))$ is minimal and a counterexample to the problem. Our result implies the existence of interesting new counterexamples including one with $n=3$ and $[k({\bf x}):L]=2$.
• We explain a connection between the algebraic and geometric properties of groups of contact transformations, open book decompositions, and flexible Legendrian embeddings. The main result is that, if a closed contact manifold $(V, \xi)$ has a supporting open book whose pages are flexible Weinstein manifolds, then both the connected component of identity in its automorphism group and its universal cover are uniformly simple groups: for every non-trivial element $g$, every other element is a product of at most $128(\dim V + 1)$ conjugates of $g^{\pm 1}$. In particular any conjugation invariant norm on these groups is bounded.
• A source submits status updates to a network for delivery to a destination monitor. Updates follow a route through a series of network nodes. Each node is a last-come-first-served queue supporting preemption in service. We characterize the average age of information at the input and output of each node in the route induced by the updates passing through. For Poisson arrivals to a line network of preemptive memoryless servers, we show that average age accumulates through successive network nodes.
• For every fixed genus $g\geq 1$, we consider all quadruples $Q=(w_0,w_1,w_2,d)\in\mathbb{Z}^4_{>0}$ with the property that any smooth degree-$d$ curve embedded in the weighted projective plane $\mathbb{P}^2(w_0,w_1,w_2)$ has genus $g$. We show there are infinitely many quadruples $Q$ satisfying this condition. For every such $Q$, we consider $Z_Q\subseteq M_g$ the locus in the moduli space of all smooth degree-$d$ curves embedded in $\mathbb{P}^2(w_0,w_1,w_2)$. We show that, as $Q$ varies over all these quadruples, there are only finitely many different loci $Z_Q\subseteq M_g$.
• In this paper we study the Dirichlet eigenvalue problem $$-\Delta_p u-\Delta_J,pu =\lambda|u|^p-2u \quad \text in \Omega,\quad u=0 \quad\text in \Omega^c=\mathbbR^N∖\Omega.$$ Here $\Delta_p u$ is the standard local $p-$Laplacian, $\Delta_{J,p}u$ is a nonlocal, $p-$homogeneous operator of order zero and $\Omega$ is a bounded domain in $\mathbb{R}^N$. We show that the first eigenvalue (that is isolated and simple) satisfies $(\lambda_1)^{1/p}\to \Lambda$ as $p\to\infty$ where $\Lambda$ can be characterized in terms of the geometry of $\Omega$. We also find that the eigenfunctions converge, $u_\infty=\lim_{p\to\infty} u_p$, and find the limit problem that is satisfied in the limit.
• This paper considers a class of real-time decision making problems to minimize the expected value of a function that depends on a random variable $\xi$ under an unknown distribution $\mathbb{P}$. In this process, samples of $\xi$ are collected sequentially in real time, and the decisions are made, using the real-time data, to guarantee out-of-sample performance. We approach this problem in a distributionally robust optimization framework and propose a novel Online Data Assimilation Algorithm for this purpose. This algorithm guarantees the out-of-sample performance in high probability, and gradually improves the quality of the data-driven decisions by incorporating the streaming data. We show that the Online Data Assimilation Algorithm guarantees convergence under the streaming data, and a criteria for termination of the algorithm after certain number of data has been collected.
• Let $\Omega\subset\mathbb R^{n+1}$ be an open set with $n$-AD-regular boundary. In this paper we prove that if the harmonic measure for $\Omega$ satisfies the so-called weak-$A_\infty$ condition, then $\Omega$ satisfies a suitable connectivity condition, namely the weak local John condition. This yields the first geometric characterization of the weak-$A_\infty$ condition of harmonic measure, which is important because its connection with the Dirichlet problem for the Laplace equation.
• We consider the problem of finding the isolated common roots of a set of polynomial functions defining a zero-dimensional ideal I in a ring R of polynomials over C. Normal form algorithms provide an algebraic approach to solve this problem. We use new characterizations of normal forms and describe accurate and efficient constructions that allow us to compute the algebra structure of R/I, and hence the solutions of I. We show how the resulting algorithms give accurate results in double precision arithmetic and compare with normal form algorithms using Groebner bases and homotopy solvers.
• Recent progress has been made with Adaptive Multiple Importance Sampling (AMIS) methods that show improvement in effective sample size. However, consistency for the AMIS estimator has only been established in very restricted cases. Furthermore, the high computational complexity of the re-weighting in AMIS (called balance heuristic) makes it expensive for applications involving diffusion processes. In this work we consider sequential and adaptive importance sampling that is particularly suitable for diffusion processes. We propose a new discarding-re-weighting scheme that is of lower computational complexity, and we prove that the resulting AMIS is consistent. Using numerical experiments, we demonstrate that discarding-re-weighting performs very similar to the balance heuristic, but at a fraction of the computational cost.
• A Gallai coloring is a coloring of the edges of a complete graph without rainbow triangles, and a Gallai $k$-coloring is a Gallai coloring that uses $k$ colors. Given an integer $k\ge1$ and graphs $H_1, H_2, \ldots, H_k$, the Gallai-Ramsey number $GR(H_1, H_2, \ldots, H_k)$ is the least integer $n$ such that every Gallai $k$-coloring of the complete graph $K_n$ contains a monochromatic copy of $H_i$ in color $i$ for some $i \in \{1,2, \ldots, k\}$. When $H = H_1 = \cdots = H_k$, we simply write $GR_k(H)$. We study Gallai-Ramsey numbers of even cycles and paths. For all $n\ge3$ and $k\ge1$, let $G_i=P_{2i+3}$ be a path on $2i+3$ vertices for all $i\in\{0,1, \ldots, n-2\}$ and $G_{n-1}\in\{C_{2n}, P_{2n+1}\}$. Let $i_j\in\{0,1,\ldots, n-1 \}$ for all $j\in\{1,2, \ldots, k\}$ with $i_1\ge i_2\ge\cdots\ge i_k$. The first author recently conjectured that $GR(G_{i_1}, G_{i_2}, \ldots, G_{i_k}) = 3+\min\{i_1,n^*-2\}+\sum_{j=1}^k i_j$, where $n^* =n$ when $G_{i_1}\ne P_{2n+1}$ and $n^* =n+1$ when $G_{i_1}= P_{2n+1}$. The truth of this conjecture implies that $GR_k(C_{2n})=GR_k(P_{2n})=(n-1)k+n+1$ for all $n\ge3$ and $k\ge1$, and $GR_k(P_{2n+1})=(n-1)k+n+2$ for all $n\ge1$ and $k\ge1$. In this paper, we prove that the aforementioned conjecture holds for $n\in\{3,4\}$ and all $k\ge1$. Our proof relies only on Gallai's result and the classical Ramsey numbers $R(H_1, H_2)$, where $H_1, H_2\in\{C_8, C_6, P_7, P_5, P_3\}$. We believe the recoloring method we developed here will be very useful for solving subsequent cases, and perhaps the conjecture.
• The Kuramoto--Sakaguchi model is a modification of the well-known Kuramoto model that adds a phase-lag paramater, or "frustration" to a network of phase-coupled oscillators. The Kuramoto model is a flow of gradient type, but adding a phase-lag breaks the gradient structure, significantly complicating the analysis of the model. We present several results determining the stability of phase-locked configurations: the first of these gives a sufficient condition for stability, and the second a sufficient condition for instability. (In fact, the instability criterion gives a count, modulo 2, of the dimension of the unstable manifold to a fixed point and having an odd count is a sufficient condition for instability of the fixed point.) We also present numerical results for both small and large collections of Kuramoto--Sakaguchi oscillators.
• We study transportation networks controlled by dynamical feedback tolls. We consider a multiscale model in which the dynamics of the traffic flows are intertwined with those of the drivers' route choices. The latter are influenced by the congestion status of the whole network as well as decentralized congestion-dependent tolls. Our main result shows that positive increasing decentralized congestion-dependent tolls allow the system planner to globally stabilise the transportation network around the Wardrop equilibrium. Moreover, using the decentralized marginal costs tolls the stability of the transportation network is around the social optimum traffic assignment.This particularly remarkable as such feedback tolls do not require any global information about the network structure or state and can be computed in a fully local way. We also extend this stability analysis to a constant decentralised feedback tolls and compare their performance both asymptotic and during the transient through numerical simulations.
• In The factorization of the Giry monad (arXiv:1707.00488v2) the author considers two $\sigma$-algebras on convex spaces of functions to the unit interval. One of them is generated by the Boolean subobjects and the other is the $\sigma$-algebra induced by the evaluation maps. The author asserts that, under the assumptions given in the paper, the two $\sigma$-algebras coincide. We give examples contradicting this statement.
• In this article, left g, h-derivation and Jordan left g, h-derivation on algebras are introduced. It is shown that there is no Jordan left g, h-derivation over $\mathcal{M}_n(C)$ and $\mathbb{H}_{\mathbb{R}}$, for g not equal to h. Examples are given which show that every Jordan left $\{g, h\}$-derivation over $\mathcal{T}_n(C)$, $\mathcal{M}_n(C)$ and $\mathbb{H}_{\mathbb{R}}$ are not left $\{g, h\}$-derivations. Moreover, we characterize left $\{g, h\}$-derivation and Jordan left $\{g, h\}$-derivation over $\mathcal{T}_n(C)$, $\mathcal{M}_n(C)$ and $\mathbb{H}_{\mathbb{R}}$ respectively. Also, we prove the result of Jordan left $\{g, h\}$-derivation to be a left $\{g, h\}$-derivation over tensor products of algebras as well as for algebra of polynomials.
• We confirm Demailly's conjecture on the convergence of higher Lelong numbers under the canonical approximation of a plurisubharmonic function in the case when the function is toric and in the Cegrell class. As applications to convex geometry, we give a unified analytic proof of the Alexandrov-Fenchel inequalities for mixed Monge-Ampère masses, mixed covolumes and mixed multiplicities.
• In this paper, we deal with the following nonlinear Schrödinger equation $$-\epsilon^2∆u+V(x)u=f(u),\ u∈H^1(\mathbb R^2),$$ where $f(t)$ has critical growth of Trudinger-Moser type. By using the variational techniques, we construct a positive solution $u_\epsilon$ concentrating around the saddle points of the potential $V(x)$ as $\epsilon\rightarrow 0$. Our results complete the analysis made in \citeMR2900480 and \citeMR3426106, where the Schrödinger equation was studied in $\mathbb R^N$, $N\geq 3$ for sub-critical and critical case respectively in the sense of Sobolev embedding. Moreover, we relax the monotonicity condition on the nonlinear term $f(t)/t$ together with a compactness assumption on the potential $V(x)$, imposed in \citeMR3503193.
• In this article, we show that every Jordan g, h-derivation over T_n(C) is a g, h-derivation under an assumption, where C is a commutative ring with unity 1 not equal to 0. We give an example of a Jordan g, h-derivation over T_n(C) which is not a g, h-derivation. Also, we study Jordan g, h-derivation over M_n(C).
• Let C be a commutative ring with unity. In this article, we show that every Jordan derivation over an upper triangular matrix algebra T_n(C) is an inner derivation. Further, we extend the result for Jordan derivation on full matrix algebra M_n(C).

Danial Dervovic Mar 01 2018 12:08 UTC

Hello again Māris, many thanks for your patience. Your comments and questions have given me much food for thought, and scope for an amended version of the paper -- please see my responses below.

Please if any of the authors of [AST17 [arXiv:1712.01609](https://arxiv.org/abs/1712.01609)] have any fu

...(continued)
Danial Dervovic Feb 05 2018 15:03 UTC

Thank you Māris for the extremely well thought-out and articulated points here.

I think this very clearly highlights the need to think explicitly about the precompute time if using the lifting to directly simulate the quantum walk, amongst other things.

I wish to give a well-considered respons

...(continued)
Māris Ozols Feb 01 2018 17:53 UTC

This paper considers the problem of using "lifted" Markov chains to simulate the mixing of coined quantum walks. The Markov chain has to approximately (in the total variational distance) sample from the distribution obtained by running the quantum walk for a randomly chosen time $t \in [0,T]$ follow

...(continued)
Marco Piani Jan 28 2018 11:21 UTC

Hi Mizanur,

thanks to you for taking into account my comment. I am not sure of the jargon and nomenclature in mathematics; are/were the maps that are completely positive and also completely co-positive known as PPT maps? What I was pointing out is that in the quantum information community the nam

...(continued)
Mizanur Rahaman Jan 27 2018 19:06 UTC

Hi Marco, thanks for pointing out the possible confusion. I will make it clear in the revised version. I think in this context what I should clearly state is that I am considering linear maps
which are completely positive and co-completely positive, that is, the map \Phi and \Phi\circleT
are compl

...(continued)
Marco Piani Jan 24 2018 03:34 UTC

Great work! One thing that might potentially confuse readers is the use of "PPT channel" to indicate that the partial action of the channel produces a PPT state. There might be some ambiguity in literature, but many call "PPT channels" those channels that act jointly on two parties, and that preserv

...(continued)
Mizanur Rahaman Jan 23 2018 23:20 UTC

Thanks for the comment. I was not aware of the "entanglement breaking index" paper.
I will include it in a revised version. I will make a remark about the other deduction as well.
Thanks.

Ludovico Lami Jan 19 2018 00:08 UTC

Very nice work, congratulations! I just want to point out that the "index of separability" had already been defined in arXiv:1411.2517, where it was called "entanglement-breaking index" and studied in some detail. The channels that have a finite index of separability had been dubbed "entanglement-sa

...(continued)
Steve Flammia Dec 18 2017 20:59 UTC

It splits into even and odd cases, actually. I was originally sloppy about the distinction between integer and polynomial division, but it's fixed now. There is a little room left in the case $d=3$ now though, but it's still proven in every other dimension.

Aram Harrow Dec 18 2017 19:30 UTC

whoa, awesome! But why do you get that $d^3-d$ must be a divisor instead of $(d^3-d)/2$?


text:
# How does the RCPSP's precedence constraint work?

In [1] the authors define the RCPSP (resource-constrained project scheduling problem) as follows:

minimize $$\sum_{t} t x_{n t}$$ subject to $$\begin{array}{c} \sum_{t} x_{j t}=1, \quad j \in J, \\ \sum_{s=t}^{T} x_{i s}+\sum_{s=0}^{t+d_{i j}-1} x_{j s} \leq 1, \quad(i, j) \in L, t=0, \ldots, T, \\ x_{j t} \geq 0, \quad j \in J, t=0, \ldots, T, \\ x_{j t} \text { integer, } \quad j \in J, t=0, \ldots, T \\ \sum_{j} r_{j k}\left(\sum_{s=t-p_{j}+1}^{t} x_{j s}\right) \leq R_{k}, k \in R, t=0, \ldots, T . \end{array}$$

What I do not understand here is the second constraint, which is the precedence constraint. Why do we need the sum $$\sum_{s=t}^{T} x_{i s}$$ and cannot just use $$x_{i t}$$ instead? Would'nt $$x_{i t}+\sum_{s=0}^{t+d_{i j}-1} x_{j s} \leq 1, \quad(i, j) \in L, t=0, \ldots, T \\$$ be enough to be sure that if the predecessor starts at time t the successor j cannot start at any time before $$t+d_{i j}$$, when $$d_{i j}$$ is the enforced time lag between the predecessor i and succesor j (which equals the duration of the predecessor if we have strict finish-start precedence constraints)?

[1] Möhring, Rolf H.; Schulz, Andreas S.; Stork, Frederik; Uetz, Marc (2003): Solving Project Scheduling Problems by Minimum Cut Computations. In: Management Science 49 (3), S. 330–350. DOI: 10.1287/mnsc.49.3.330.12737.

• Many thanks for your suggestion. would you say please, if the following constraints are replaced instead of the second constraints, is there any reasonable change in the complexity of the model? $\sum_{t\in \mathcal{T}} t\cdot x_{(i,t)} - \sum_{t \in \mathcal{T}} t\cdot x_{(j,t)} \geq p_{j} \,\,\, \quad \forall (i,j) \in L_{(i,j)}$ Where $p_j$ is the processing time of job $j$. Apr 4 at 8:42
• @A.Omidi it looks like you have $i$ and $j$ reversed, but that idea also works. Not sure which will perform better. Apr 4 at 13:12

format: plain


text:
# Topological group explained

In mathematics, topological groups are logically the combination of groups and topological spaces, i.e. they are groups and topological spaces at the same time, such that the continuity condition for the group operations connects these two structures together and consequently they are not independent from each other.

Topological groups have been studied extensively in the period of 1925 to 1940. Haar and Weil (respectively in 1933 and 1940) showed that the integrals and Fourier series are special cases of a very wide class of topological groups.

Topological groups, along with continuous group actions, are used to study continuous symmetries, which have many applications, for example, in physics. In functional analysis, every topological vector space is an additive topological group with the additional property that scalar multiplication is continuous; consequently, many results from the theory of topological groups can be applied to functional analysis.

## Formal definition

A topological group,, is a topological space that is also a group such that the group operation (in this case product):

, and the inversion map:

, are continuous.[1] Here is viewed as a topological space with the product topology. Such a topology is said to be compatible with the group operations and is called a group topology.

Checking continuity

The product map is continuous if and only if for any and any neighborhood of in, there exist neighborhoods of and of in such that, where . The inversion map is continuous if and only if for any and any neighborhood of in, there exists a neighborhood of in such that, where .

To show that a topology is compatible with the group operations, it suffices to check that the map

, is continuous. Explicitly, this means that for any and any neighborhood in of, there exist neighborhoods of and of in such that .

This definition used notation for multiplicative groups; the equivalent for additive groups would be that the following two operations are continuous:

,

, .

Hausdorffness

Although not part of this definition, many authors require that the topology on be Hausdorff. One reason for this is that any topological group can be canonically associated with a Hausdorff topological group by taking an appropriate canonical quotient; this however, often still requires working with the original non-Hausdorff topological group.Other reasons, and some equivalent conditions, are discussed below.

Category

In the language of category theory, topological groups can be defined concisely as group objects in the category of topological spaces, in the same way that ordinary groups are group objects in the category of sets. Note that the axioms are given in terms of the maps (binary product, unary inverse, and nullary identity), hence are categorical definitions.

### Homomorphisms

A homomorphism of topological groups means a continuous group homomorphism . Topological groups, together with their homomorphisms, form a category. A group homomorphism between commutative topological groups is continuous if and only if it is continuous at some point.

An isomorphism of topological groups is a group isomorphism that is also a homeomorphism of the underlying topological spaces. This is stronger than simply requiring a continuous group isomorphism—the inverse must also be continuous. There are examples of topological groups that are isomorphic as ordinary groups but not as topological groups. Indeed, any non-discrete topological group is also a topological group when considered with the discrete topology. The underlying groups are the same, but as topological groups there is not an isomorphism.

## Examples

Every group can be trivially made into a topological group by considering it with the discrete topology; such groups are called discrete groups. In this sense, the theory of topological groups subsumes that of ordinary groups. The indiscrete topology (i.e. the trivial topology) also makes every group into a topological group.

The real numbers,

R

with the usual topology form a topological group under addition. Euclidean -space is also a topological group under addition, and more generally, every topological vector space forms an (abelian) topological group. Some other examples of abelian topological groups are the circle group, or the torus for any natural number .

The classical groups are important examples of non-abelian topological groups. For instance, the general linear group of all invertible -by- matrices with real entries can be viewed as a topological group with the topology defined by viewing as a subspace of Euclidean space . Another classical group is the orthogonal group, the group of all linear maps from to itself that preserve the length of all vectors. The orthogonal group is compact as a topological space. Much of Euclidean geometry can be viewed as studying the structure of the orthogonal group, or the closely related group of isometries of .

The groups mentioned so far are all Lie groups, meaning that they are smooth manifolds in such a way that the group operations are smooth, not just continuous. Lie groups are the best-understood topological groups; many questions about Lie groups can be converted to purely algebraic questions about Lie algebras and then solved.

An example of a topological group that is not a Lie group is the additive group

Q

of rational numbers, with the topology inherited from

R

. This is a countable space, and it does not have the discrete topology. An important example for number theory is the group of p-adic integers, for a prime number, meaning the inverse limit of the finite groups as n goes to infinity. The group is well behaved in that it is compact (in fact, homeomorphic to the Cantor set), but it differs from (real) Lie groups in that it is totally disconnected. More generally, there is a theory of p-adic Lie groups, including compact groups such as as well as locally compact groups such as, where is the locally compact field of p-adic numbers.

The group is a pro-finite group; it is isomorphic to a subgroup of the product

\prodnZ/pn

in such a way that its topology is induced by the product topology, where the finite groups

Z/pn

are given the discrete topology. Another large class of pro-finite groups important in number theory are absolute Galois groups.

Some topological groups can be viewed as infinite dimensional Lie groups; this phrase is best understood informally, to include several different families of examples. For example, a topological vector space, such as a Banach space or Hilbert space, is an abelian topological group under addition. Some other infinite-dimensional groups that have been studied, with varying degrees of success, are loop groups, Kac–Moody groups, diffeomorphism groups, homeomorphism groups, and gauge groups.

In every Banach algebra with multiplicative identity, the set of invertible elements forms a topological group under multiplication. For example, the group of invertible bounded operators on a Hilbert space arises this way.

## Properties

### Translation invariance

Every topological group's topology is, which by definition means that if for any

a\inG,

left or right multiplication by this element yields a homeomorphism

G\toG.

Consequently, for any

a\inG

and

S\subseteqG,

the subset

S

is open (resp. closed) in

G

if and only if this is true of its left translation

aS:=\{as:s\inS\}

and right translation

Sa:=\{sa:s\inS\}.

If

l{N}

is a neighborhood basis of the identity element in a commutative topological group

G

then for all

x\inX,

$x \mathcal := \$is a neighborhood basis of

x

in

G.

In particular, any group topology on a commutative topological group is completely determined by any neighborhood basis at the identity element. If

S

is any subset of

G

and

U

is an open subset of

G,

then

SU:=\{su:s\inS,u\inU\}

is an open subset of

G.

### Symmetric neighborhoods

The inversion operation

g\mapstog-1

on a topological group

G

is a homeomorphism from

G

to itself.

A subset

S\subseteqG

is said to be symmetric if

S-1=S,

where

S-1:=\left\{s-1:s\inS\right\}.

The closure of every symmetric set in a commutative topological group is symmetric. If is any subset of a commutative topological group, then the following sets are also symmetric:,, and .

For any neighborhood in a commutative topological group of the identity element, there exists a symmetric neighborhood of the identity element such that, where note that is necessarily a symmetric neighborhood of the identity element. Thus every topological group has a neighborhood basis at the identity element consisting of symmetric sets.

If is a locally compact commutative group, then for any neighborhood in of the identity element, there exists a symmetric relatively compact neighborhood of the identity element such that (where is symmetric as well).

### Uniform space

Every topological group can be viewed as a uniform space in two ways; the left uniformity turns all left multiplications into uniformly continuous maps while the right uniformity turns all right multiplications into uniformly continuous maps.If is not abelian, then these two need not coincide. The uniform structures allow one to talk about notions such as completeness, uniform continuity and uniform convergence on topological groups.

### Separation properties

If is an open subset of a commutative topological group and contains a compact set, then there exists a neighborhood of the identity element such that .

As a uniform space, every commutative topological group is completely regular. Consequently, for a multiplicative topological group with identity element 1, the following are equivalent:

1. is a T0-space (Kolmogorov);
2. is a T2-space (Hausdorff);
3. is a T3 (Tychonoff);
4. is closed in ;
5. , where is a neighborhood basis of the identity element in ;
6. for any

x\inG

such that

x1,

there exists a neighborhood in of the identity element such that

x\not\inU.

A subgroup of a commutative topological group is discrete if and only if it has an isolated point.

If is not Hausdorff, then one can obtain a Hausdorff group by passing to the quotient group, where is the closure of the identity. This is equivalent to taking the Kolmogorov quotient of .

### Metrisability

Let be a topological group. As with any topological space, we say that is metrisable if and only if there exists a metric on, which induces the same topology on

G

. A metric on is called
• left-invariant (resp. right-invariant) if and only if

d(ax1,ax2)=d(x1,x2)

(resp.

d(x1a,x2a)=d(x1,x2)

) for all

a,x1,x2\inG

(equivalently,

d

is left-invariant just in case the map

x\mapstoax

is an isometry from

(G,d)

to itself for each

a\inG

).
• proper if and only if all open balls,

B(r)=\{g\inG\midd(g,1)<r\}

for

r>0

, are pre-compact.The Birkhoff–Kakutani theorem (named after mathematicians Garrett Birkhoff and Shizuo Kakutani) states that the following three conditions on a topological group are equivalent:
1. is first countable (equivalently: the identity element 1 is closed in, and there is a countable basis of neighborhoods for 1 in).
2. is metrisable (as a topological space).
3. There is a left-invariant metric on that induces the given topology on .

Furthermore, the following are equivalent for any topological group :

1. is a second countable locally compact (Hausdorff) space.
2. is a Polish, locally compact (Hausdorff) space.
3. is properly metrisable (as a topological space).
4. There is a left-invariant, proper metric on that induces the given topology on .

Note: As with the rest of the article we of assume here a Hausdorff topology.The implications 4

3

2

1 hold in any topological space. In particular 3

2 holds, since in particular any properly metrisable space is countable union of compact metrisable and thus separable (cf. properties of compact metric spaces) subsets.The non-trivial implication 1

4 was first proved by Raimond Struble in 1974.[2] An alternative approach was made by Uffe Haagerup and Agata Przybyszewska in 2006,the idea of the which is as follows:One relies on the construction of a left-invariant metric,

d0

, as in the case of first countable spaces. By local compactness, closed balls of sufficiently small radii are compact, and by normalising we can assume this holds for radius 1. Closing the open ball,, of radius 1 under multiplication yields a clopen subgroup,, of, on which the metric

d0

is proper. Since is open and is second countable, the subgroup has at most countably many cosets. One now uses this sequence of cosets and the metric on to construct a proper metric on .

### Subgroups

Every subgroup of a topological group is itself a topological group when given the subspace topology. Every open subgroup is also closed in, since the complement of is the open set given by the union of open sets for . If is a subgroup of then the closure of is also a subgroup. Likewise, if is a normal subgroup of, the closure of is normal in .

### Quotients and normal subgroups

If is a subgroup of, the set of left cosets with the quotient topology is called a homogeneous space for . The quotient map

q:G\toG/H

is always open. For example, for a positive integer, the sphere is a homogeneous space for the rotation group in, with . A homogeneous space is Hausdorff if and only if is closed in . Partly for this reason, it is natural to concentrate on closed subgroups when studying topological groups.

If is a normal subgroup of, then the quotient group becomes a topological group when given the quotient topology. It is Hausdorff if and only if is closed in . For example, the quotient group is isomorphic to the circle group .

In any topological group, the identity component (i.e., the connected component containing the identity element) is a closed normal subgroup. If is the identity component and a is any point of, then the left coset is the component of containing a. So the collection of all left cosets (or right cosets) of in is equal to the collection of all components of . It follows that the quotient group is totally disconnected.

### Closure and compactness

In any commutative topological group, the product (assuming the group is multiplicative) of a compact set and a closed set is a closed set. Furthermore, for any subsets and of, .

If is a subgroup of a commutative topological group and if is a neighborhood in of the identity element such that is closed, then is closed. Every discrete subgroup of a Hausdorff commutative topological group is closed.

### Isomorphism theorems

The isomorphism theorems from ordinary group theory are not always true in the topological setting. This is because a bijective homomorphism need not be an isomorphism of topological groups.

For example, a native version of the first isomorphism theorem is false for topological groups: if

f:G\toH

is a morphism of topological groups (that is, a continuous homomorphism), it is not necessarily true that the induced homomorphism

\tilde{f}:G/\kerf\toIm(f)

is an isomorphism of topological groups; it will be a bijective, continuous homomorphism, but it will not necessarily be a homeomorphism. In other words, it will not necessarily admit an inverse in the category of topological groups.

There is a version of the first isomorphism theorem for topological groups, which may be stated as follows: if

f:G\toH

is a continuous homomorphism, then the induced homomorphism from to is an isomorphism if and only if the map is open onto its image.

The third isomorphism theorem, however, is true more or less verbatim for topological groups, as one may easily check.

## Hilbert's fifth problem

There are several strong results on the relation between topological groups and Lie groups. First, every continuous homomorphism of Lie groups

G\toH

is smooth. It follows that a topological group has a unique structure of a Lie group if one exists. Also, Cartan's theorem says that every closed subgroup of a Lie group is a Lie subgroup, in particular a smooth submanifold.

Hilbert's fifth problem asked whether a topological group that is a topological manifold must be a Lie group. In other words, does have the structure of a smooth manifold, making the group operations smooth? As shown by Andrew Gleason, Deane Montgomery, and Leo Zippin, the answer to this problem is yes. In fact, has a real analytic structure. Using the smooth structure, one can define the Lie algebra of, an object of linear algebra that determines a connected group up to covering spaces. As a result, the solution to Hilbert's fifth problem reduces the classification of topological groups that are topological manifolds to an algebraic problem, albeit a complicated problem in general.

The theorem also has consequences for broader classes of topological groups. First, every compact group (understood to be Hausdorff) is an inverse limit of compact Lie groups. (One important case is an inverse limit of finite groups, called a profinite group. For example, the group of p-adic integers and the absolute Galois group of a field are profinite groups.) Furthermore, every connected locally compact group is an inverse limit of connected Lie groups. At the other extreme, a totally disconnected locally compact group always contains a compact open subgroup, which is necessarily a profinite group. (For example, the locally compact group contains the compact open subgroup, which is the inverse limit of the finite groups as ' goes to infinity.)

## Representations of compact or locally compact groups

An action of a topological group on a topological space X is a group action of on X such that the corresponding function is continuous. Likewise, a representation of a topological group on a real or complex topological vector space V is a continuous action of on V such that for each, the map from V to itself is linear.

Group actions and representation theory are particularly well understood for compact groups, generalizing what happens for finite groups. For example, every finite-dimensional (real or complex) representation of a compact group is a direct sum of irreducible representations. An infinite-dimensional unitary representation of a compact group can be decomposed as a Hilbert-space direct sum of irreducible representations, which are all finite-dimensional; this is part of the Peter–Weyl theorem. For example, the theory of Fourier series describes the decomposition of the unitary representation of the circle group on the complex Hilbert space . The irreducible representations of are all 1-dimensional, of the form for integers (where is viewed as a subgroup of the multiplicative group *). Each of these representations occurs with multiplicity 1 in .

The irreducible representations of all compact connected Lie groups have been classified. In particular, the character of each irreducible representation is given by the Weyl character formula.

More generally, locally compact groups have a rich theory of harmonic analysis, because they admit a natural notion of measure and integral, given by the Haar measure. Every unitary representation of a locally compact group can be described as a direct integral of irreducible unitary representations. (The decomposition is essentially unique if is of Type I, which includes the most important examples such as abelian groups and semisimple Lie groups.) A basic example is the Fourier transform, which decomposes the action of the additive group

R

on the Hilbert space as a direct integral of the irreducible unitary representations of

R

. The irreducible unitary representations of

R

are all 1-dimensional, of the form for .

The irreducible unitary representations of a locally compact group may be infinite-dimensional. A major goal of representation theory, related to the Langlands classification of admissible representations, is to find the unitary dual (the space of all irreducible unitary representations) for the semisimple Lie groups. The unitary dual is known in many cases such as, but not all.

For a locally compact abelian group, every irreducible unitary representation has dimension 1. In this case, the unitary dual

\hat{G}

is a group, in fact another locally compact abelian group. Pontryagin duality states that for a locally compact abelian group, the dual of

\hat{G}

is the original group . For example, the dual group of the integers is the circle group, while the group

R

of real numbers is isomorphic to its own dual.

Every locally compact group has a good supply of irreducible unitary representations; for example, enough representations to distinguish the points of (the Gelfand–Raikov theorem). By contrast, representation theory for topological groups that are not locally compact has so far been developed only in special situations, and it may not be reasonable to expect a general theory. For example, there are many abelian Banach–Lie groups for which every representation on Hilbert space is trivial.

## Homotopy theory of topological groups

Topological groups are special among all topological spaces, even in terms of their homotopy type. One basic point is that a topological group determines a path-connected topological space, the classifying space (which classifies principal -bundles over topological spaces, under mild hypotheses). The group is isomorphic in the homotopy category to the loop space of ; that implies various restrictions on the homotopy type of . Some of these restrictions hold in the broader context of H-spaces.

For example, the fundamental group of a topological group is abelian. (More generally, the Whitehead product on the homotopy groups of is zero.) Also, for any field k, the cohomology ring has the structure of a Hopf algebra. In view of structure theorems on Hopf algebras by Heinz Hopf and Armand Borel, this puts strong restrictions on the possible cohomology rings of topological groups. In particular, if is a path-connected topological group whose rational cohomology ring is finite-dimensional in each degree, then this ring must be a free graded-commutative algebra over

Q

, that is, the tensor product of a polynomial ring on generators of even degree with an exterior algebra on generators of odd degree.

In particular, for a connected Lie group, the rational cohomology ring of is an exterior algebra on generators of odd degree. Moreover, a connected Lie group has a maximal compact subgroup K, which is unique up to conjugation, and the inclusion of K into is a homotopy equivalence. So describing the homotopy types of Lie groups reduces to the case of compact Lie groups. For example, the maximal compact subgroup of is the circle group, and the homogeneous space can be identified with the hyperbolic plane. Since the hyperbolic plane is contractible, the inclusion of the circle group into is a homotopy equivalence.

Finally, compact connected Lie groups have been classified by Wilhelm Killing, Élie Cartan, and Hermann Weyl. As a result, there is an essentially complete description of the possible homotopy types of Lie groups. For example, a compact connected Lie group of dimension at most 3 is either a torus, the group SU(2) (diffeomorphic to the 3-sphere), or its quotient group (diffeomorphic to).

## Complete topological group

Information about convergence of nets and filters, such as definitions and properties, can be found in the article about filters in topology.

### Canonical uniformity on a commutative topological group

See main article: Uniform space.

This article will henceforth assume that any topological group that we consider is an additive commutative topological group with identity element

0.

The diagonal of

X

is the set$\Delta_X := \$and for any

N\subseteqX

containing

0,

the canonical entourage or canonical vicinities around

N

is the set$\Delta_X(N) := \ = \bigcup_ [(y + N) \times \{y\}] = \Delta_X + (N \times \)$

For a topological group

(X,\tau),

the canonical uniformity on

X

is the uniform structure induced by the set of all canonical entourages

\Delta(N)

as

N

ranges over all neighborhoods of

0

in

X.

That is, it is the upward closure of the following prefilter on

X x X,

$\left\$where this prefilter forms what is known as a base of entourages of the canonical uniformity.

X,

a fundamental system of entourages

l{B}

is called a translation-invariant uniformity if for every

B\inl{B},

(x,y)\inB

if and only if

(x+z,y+z)\inB

for all

x,y,z\inX.

A uniformity

l{B}

is called translation-invariant if it has a base of entourages that is translation-invariant.

• The canonical uniformity on any commutative topological group is translation-invariant.
• The same canonical uniformity would result by using a neighborhood basis of the origin rather the filter of all neighborhoods of the origin.
• Every entourage

\DeltaX(N)

contains the diagonal

\DeltaX:=\DeltaX(\{0\})=\{(x,x):x\inX\}

because

0\inN.

• If

N

is symmetric (that is,

-N=N

) then

\DeltaX(N)

is symmetric (meaning that
 \operatorname{op \Delta X(N)
} = \Delta_X(N)) and

\DeltaX(N)\circ\DeltaX(N)=\{(x,z):thereexistsy\inXsuchthatx,z\iny+N\}=cupy[(y+N) x (y+N)]=\DeltaX+(N x N).

• The topology induced on

X

by the canonical uniformity is the same as the topology that

X

started with (that is, it is

\tau

).

### Cauchy prefilters and nets

See main article: Filters in topology and Net (mathematics).

The general theory of uniform spaces has its own definition of a "Cauchy prefilter" and "Cauchy net." For the canonical uniformity on

X,

these reduces down to the definition described below.

Suppose

x\bull=\left(xi\right)i

is a net in

X

and

y\bull=\left(yj\right)j

is a net in

Y.

Make

I x J

into a directed set by declaring

(i,j)\leq\left(i2,j2\right)

if and only if

i\leqi2andj\leqj2.

Then

x\bull x y\bull:=\left(xi,yj\right)(i,

denotes the product net. If

X=Y

then the image of this net under the addition map

X x X\toX

denotes the sum of these two nets:$x_ + y_: = \left(x_i + y_j\right)_$and similarly their difference is defined to be the image of the product net under the subtraction map:$x_ - y_: = \left(x_i - y_j\right)_.$

x\bull=\left(xi\right)i

X

is called a Cauchy net if$\left(x_i - x_j\right)_ \to 0 \text X$or equivalently, if for every neighborhood

N

of

0

in

X,

there exists some

i0\inI

such that

xi-xj\inN

for all indices

i,j\geqi0.

A Cauchy sequence is a Cauchy net that is a sequence.

If

B

is a subset of an additive group

X

and

N

is a set containing

0,

then

B

is said to be an

N

-small set
or small of order

N

if

B-B\subseteqN.

A prefilter

l{B}

X

called a Cauchy prefilter if it satisfies any of the following equivalent conditions:
1. l{B}-l{B}\to0

in

X,

where

l{B}-l{B}:=\{B-C:B,C\inl{B}\}

is a prefilter.
2. \{B-B:B\inl{B}\}\to0

in

X,

where

\{B-B:B\inl{B}\}

is a prefilter equivalent to

l{B}-l{B}.

3. For every neighborhood

N

of

0

in

X,

l{B}

contains some

N

-small set (that is, there exists some

B\inl{B}

such that

B-B\subseteqN

).
and if

X

is commutative then also:
1. For every neighborhood

N

of

0

in

X,

there exists some

B\inl{B}

and some

x\inX

such that

B\subseteqx+N.

• It suffices to check any of the above condition for any given neighborhood basis of

0

in

X.

Suppose

l{B}

is a prefilter on a commutative topological group

X

and

x\inX.

Then

l{B}\tox

in

X

if and only if

x\in\operatorname{cl}l{B}

and

l{B}

is Cauchy.

### Complete commutative topological group

Recall that for any

S\subseteqX,

a prefilter

l{C}

on

S

is necessarily a subset of

\wp(S)

; that is,

l{C}\subseteq\wp(S).

A subset

S

of a topological group

X

is called a complete subset if it satisfies any of the following equivalent conditions:
1. Every Cauchy prefilter

l{C}\subseteq\wp(S)

on

S

converges to at least one point of

S.

• If

X

is Hausdorff then every prefilter on

S

will converge to at most one point of

X.

But if

X

is not Hausdorff then a prefilter may converge to multiple points in

X.

The same is true for nets.
2. Every Cauchy net in

S

converges to at least one point of

S

;
3. Every Cauchy filter

l{C}

on

S

converges to at least one point of

S.

4. S

is a complete uniform space (under the point-set topology definition of "complete uniform space") when

S

is endowed with the uniformity induced on it by the canonical uniformity of

X

;

A subset

S

is called a sequentially complete subset if every Cauchy sequence in

S

(or equivalently, every elementary Cauchy filter/prefilter on

S

) converges to at least one point of

S.

• Importantly, convergence outside of

S

is allowed: If

X

is not Hausdorff and if every Cauchy prefilter on

S

converges to some point of

S,

then

S

will be complete even if some or all Cauchy prefilters on

S

also converge to points(s) in the complement

X\setminusS.

In short, there is no requirement that these Cauchy prefilters on

S

converge only to points in

S.

The same can be said of the convergence of Cauchy nets in

S.

• As a consequence, if a commutative topological group

X

is not Hausdorff, then every subset of the closure of

\{0\},

say

S\subseteq\operatorname{cl}\{0\},

is complete (since it is clearly compact and every compact set is necessarily complete). So in particular, if

S\varnothing

(for example, if

S

a is singleton set such as

S=\{0\}

) then

S

would be complete even though every Cauchy net in

S

(and every Cauchy prefilter on

S

), converges to every point in

\operatorname{cl}\{0\}

(include those points in

\operatorname{cl}\{0\}

that are not in

S

).
• This example also shows that complete subsets (indeed, even compact subsets) of a non-Hausdorff space may fail to be closed (for example, if

\varnothingS\subseteq\operatorname{cl}\{0\}

then

S

is closed if and only if

S=\operatorname{cl}\{0\}

).

A commutative topological group

X

is called a complete group if any of the following equivalent conditions hold:
1. X

is complete as a subset of itself.
2. Every Cauchy net in

X

converges to at least one point of

X.

3. There exists a neighborhood of

0

in

X

that is also a complete subset of

X.

• This implies that every locally compact commutative topological group is complete.

4. When endowed with its canonical uniformity,

X

becomes is a complete uniform space.
• In the general theory of uniform spaces, a uniform space is called a complete uniform space if each Cauchy filter in

X

converges in

(X,\tau)

to some point of

X.

A topological group is called sequentially complete if it is a sequentially complete subset of itself.

Neighborhood basis: Suppose

C

is a completion of a commutative topological group

X

with

X\subseteqC

and that

l{N}

is a neighborhood base of the origin in

X.

Then the family of sets $\left\$is a neighborhood basis at the origin in

C.

Let

X

and

Y

be topological groups,

D\subseteqX,

and

f:D\toY

be a map. Then

f:D\toY

is uniformly continuous if for every neighborhood

U

of the origin in

X,

there exists a neighborhood

V

of the origin in

Y

such that for all

x,y\inD,

if

y-x\inU

then

f(y)-f(x)\inV.

## Generalizations

Various generalizations of topological groups can be obtained by weakening the continuity conditions:

• A semitopological group is a group with a topology such that for each the two functions defined by and are continuous.
• A quasitopological group is a semitopological group in which the function mapping elements to their inverses is also continuous.
• A paratopological group is a group with a topology such that the group operation is continuous.

## References

• Book: Arhangel'skii. Alexander . Alexander Arhangelskii . Tkachenko. Mikhail . Topological Groups and Related Structures . . 2008 . 978-90-78677-06-2 . 2433295.
• Book: Armstrong, Mark A. . Basic Topology . . 1st . 1997 . 0-387-90839-0 . 0705632.
• Book: Pontryagin, Lev S. . Lev Pontryagin . Topological Groups . 1986 . 3rd . trans. from Russian by Arlen Brown and P.S.V. Naidu . Gordon and Breach Science Publishers . New York . 2-88124-133-6 . 0201557.
• Book: Porteous, Ian R. . Ian R. Porteous . Topological Geometry . . 1981 . 2nd . 0-521-23160-4 . 0606198.

## Notes and References

1. i.e. Continuous means that for any open set, is open in the domain of .
2. Struble. Raimond A.. 1974. Metrics in locally compact groups. Compositio Mathematica. en. 28. 3. 217–222.