Mathematics (math)

  • PDF
    Transversality is a simple and effective method for implementing quantum computation fault-tolerantly. However, no quantum error-correcting code (QECC) can transversally implement a quantum universal gate set (Eastin and Knill, Phys. Rev. Lett., 102, 110502). Since reversible classical computation is often a dominating part of useful quantum computation, whether or not it can be implemented transversally is an important open problem. We show that, other than a small set of non-additive codes that we cannot rule out, no binary QECC can transversally implement a classical reversible universal gate set. In particular, no such QECC can implement the Toffoli gate transversally. We prove our result by constructing an information theoretically secure (but inefficient) quantum homomorphic encryption (ITS-QHE) scheme inspired by Ouyang et al. (arXiv:1508.00938). Homomorphic encryption allows the implementation of certain functions directly on encrypted data, i.e. homomorphically. Our scheme builds on almost any QECC, and implements that code's transversal gate set homomorphically. We observe a restriction imposed by Nayak's bound (FOCS 1999) on ITS-QHE, implying that any ITS quantum fully homomorphic scheme (ITS-QFHE) implementing the full set of classical reversible functions must be highly inefficient. While our scheme incurs exponential overhead, any such QECC implementing Toffoli transversally would still violate this lower bound through our scheme.
  • PDF
    We derive a lower bound on the differential entropy of a log-concave random variable $X$ in terms of the $p$-th absolute moment of $X$. The new bound leads to a reverse entropy power inequality with an explicit constant, and to new bounds on the rate-distortion function and the channel capacity. Specifically, we study the rate-distortion function for log-concave sources and distortion measure $| x - \hat x|^r$, and we establish that the difference between the rate distortion function and the Shannon lower bound is at most $\log(2 \sqrt{\pi e}) \approx 2.5$ bits, independently of $r$ and the target distortion $d$. For mean-square error distortion, the difference is at most $\log (\sqrt{2 \pi e}) \approx 2$ bits, regardless of $d$. The bounds can be further strengthened if the source, in addition to being log-concave, is symmetric. In particular, we establish that for mean-square error distortion, the difference is at most $\log (\sqrt{\pi e}) \approx 1.5$ bits, regardless of $d$. We also provide bounds on the capacity of memoryless additive noise channels when the noise is log-concave. We show that the difference between the capacity of such channels and the capacity of the Gaussian channel with the same noise power is at most $\log(\sqrt {2\pi e}) \approx 2$ bits, and at most $\log (\sqrt{\pi e}) \approx 1.5$ bits if the noise is symmetric log-concave. Our results generalize to the case of vector $X$ with possibly dependent coordinates, and to $\gamma$-concave random variables. Our proof technique leverages tools from convex geometry.
  • PDF
    Many real-world control systems, such as the smart grid and human sensorimotor control systems, have decentralized components that react quickly using local information and centralized components that react slowly using a more global view. This paper seeks to provide a theoretical framework for how to design controllers that are decomposed across timescales in this way. The framework is analogous to how the network utility maximization framework uses optimization decomposition to distribute a global control problem across independent controllers, each of which solves a local problem; except our goal is to decompose a global problem temporally, extracting a timescale separation. Our results highlight that decomposition of a multi-timescale controller into a fast timescale, reactive controller and a slow timescale, predictive controller can be near-optimal in a strong sense. In particular, we exhibit such a design, named Multi-timescale Reflexive Predictive Control (MRPC), which maintains a per-timestep cost within a constant factor of the offline optimal in an adversarial setting.
  • PDF
    Principal component analysis (PCA) is a fundamental dimension reduction tool in statistics and machine learning. For large and high-dimensional data, computing the PCA (i.e., the singular vectors corresponding to a number of dominant singular values of the data matrix) becomes a challenging task. In this work, a single-pass randomized algorithm is proposed to compute PCA with only one pass over the data. It is suitable for processing extremely large and high-dimensional data stored in slow memory (hard disk) or the data generated in a streaming fashion. Experiments with synthetic and real data validate the algorithm's accuracy, which has orders of magnitude smaller error than an existing single-pass algorithm. For a set of high-dimensional data stored as a 150 GB file, the proposed algorithm is able to compute the first 50 principal components in just 24 minutes on a typical 24-core computer, with less than 1 GB memory cost.
  • PDF
    We provide criteria for the cyclotomic quiver Hecke algebras of type C to be semisimple. In the semisimple case, we construct the irreducible modules.
  • Apr 26 2017 math.ST stat.TH arXiv:1704.07513v1
    PDF
    We offer a general Bayes theoretic framework to tackle the model selection problem under a two-step prior design: the first-step prior serves to assess the model selection uncertainty, and the second-step prior quantifies the prior belief on the strength of the signals within the model chosen from the first step. We establish non-asymptotic oracle posterior contraction rates under (i) a new Bernstein-inequality condition on the log likelihood ratio of the statistical experiment, (ii) a local entropy condition on the dimensionality of the models, and (iii) a sufficient mass condition on the second-step prior near the best approximating signal for each model. The first-step prior can be designed generically. The resulting posterior mean also satisfies an oracle inequality, thus automatically serving as an adaptive point estimator in a frequentist sense. Model mis-specification is allowed in these oracle rates. The new Bernstein-inequality condition not only eliminates the need of constructing explicit tests with exponentially small type I and II errors, but also suggests the `intrinsic' metric to use in a given statistical experiment, both as a loss function and as an entropy measurement. This gives a unified reduction scheme for many experiments considered in Ghosal & van der Vaart(2007) and beyond. As an illustration for the scope of our general results in concrete applications, we consider (i) trace regression, (ii) shape-restricted isotonic/convex regression, (iii) high-dimensional partially linear regression and (iv) covariance matrix estimation in the sparse factor model. These new results serve either as theoretical justification of practical prior proposals in the literature, or as an illustration of the generic construction scheme of a (nearly) minimax adaptive estimator for a multi-structured experiment.
  • PDF
    These notes have been prepared for the Workshop on "(Non)-existence of complex structures on $\mathbb{S}^6$", to be celebrated in Marburg in March, 2017. The material is not intended to be original. It contains a survey about the smallest of the exceptional Lie groups: $G_2$, its definition and different characterizations joint with its relationship with $\mathbb{S}^6$ and with $\mathbb{S}^7$. With the exception of the summary of the Killing-Cartan classification, this survey is self-contained, and all the proofs are given, mainly following linear algebra arguments. Although these proofs are well-known, they are spread and some of them are difficult to find. The approach is algebraical, working at the Lie algebra level most of times. We analyze the complex Lie algebra (and group) of type $G_2$ as well as the two real Lie algebras of type $G_2$, the split and the compact one. Octonions will appear, but it is not the starting point. Also, 3-forms approach and spinorial approach are viewed and related.
  • PDF
    We analyze freely-acting discrete symmetries of Calabi-Yau three-folds defined as hypersurfaces in ambient toric four-folds. An algorithm which allows the systematic classification of such symmetries which are linearly realised on the toric ambient space is devised. This algorithm is applied to all Calabi-Yau manifolds with $h^{1,1}(X)\leq 3$ obtained by triangulation from the Kreuzer-Skarke list, a list of some $350$ manifolds. All previously known freely-acting symmetries on these manifolds are correctly reproduced and we find five manifolds with freely-acting symmetries. These include a single new example, a manifold with a $\mathbb{Z}_2\times\mathbb{Z}_2$ symmetry where only one of the $\mathbb{Z}_2$ factors was previously known. In addition, a new freely-acting $\mathbb{Z}_2$ symmetry is constructed for a manifold with $h^{1,1}(X)=6$. While our results show that there are more freely-acting symmetries within the Kreuzer-Skarke set than previously known, it appears that such symmetries are relatively rare.
  • PDF
    The main aim of this paper is to prove $R$-triviality for simple, simply connected algebraic groups with Tits index $E_{8,2}^{78}$ or $E_{7,1}^{78}$, defined over a field $k$ of arbitrary characteristic. Let $G$ be such a group. We prove that there exists a quadratic extension $K$ of $k$ such that $G$ is $R$-trivial over $K$, i.e., for any extension $F$ of $K$, $G(F)/R=\{1\}$, where $G(F)/R$ denotes the group of $R$-equivalence classes in $G(F)$, in the sense of Manin (see \citeM). As a consequence, it follows that the variety $G$ is retract $K$-rational and that the Kneser-Tits conjecture holds for these groups over $K$. Moreover, $G(L)$ is projectively simple as an abstract group for any field extension $L$ of $K$. In their monograph (\citeTW) J. Tits and Richard Weiss conjectured that for an Albert division algebra $A$ over a field $k$, its structure group $Str(A)$ is generated by scalar homotheties and its $U$-operators. This is known to be equivalent to the Kneser-Tits conjecture for groups with Tits index $E_{8,2}^{78}$. We settle this conjecture for Albert division algebras which are first constructions, in affirmative. These results are obtained as corollaries to the main result, which shows that if $A$ is an Albert division algebra which is a first construction and $\Gamma$ its structure group, i.e., the algebraic group of the norm similarities of $A$, then $\Gamma(F)/R=\{1\}$ for any field extension $F$ of $k$, i.e., $\Gamma$ is $R$-trivial.
  • PDF
    We obtain sharp sparse bounds for Hilbert transforms along curves in $\mathbb{R}^n$, and derive as corollaries weighted norm inequalities for such operators. The curves that we consider include monomial curves and arbitrary $C^n$ curves with nonvanishing torsion.
  • PDF
    This paper considers the problem of decentralized optimization with a composite objective containing smooth and non-smooth terms. To solve the problem, a proximal-gradient scheme is studied. Specifically, the smooth and nonsmooth terms are dealt with by gradient update and proximal update, respectively. The studied algorithm is closely related to a previous decentralized optimization algorithm, PG-EXTRA [37], but has a few advantages. First of all, in our new scheme, agents use uncoordinated step-sizes and the stable upper bounds on step-sizes are independent from network topology. The step-sizes depend on local objective functions, and they can be as large as that of the gradient descent. Secondly, for the special case without non-smooth terms, linear convergence can be achieved under the strong convexity assumption. The dependence of the convergence rate on the objective functions and the network are separated, and the convergence rate of our new scheme is as good as one of the two convergence rates that match the typical rates for the general gradient descent and the consensus averaging. We also provide some numerical experiments to demonstrate the efficacy of the introduced algorithms and validate our theoretical discoveries.
  • PDF
    We prove a compactness principle for the anisotropic formulation of the Plateau problem in any codimension, in the same spirit of the previous works of the authors \citeDelGhiMag,DePDeRGhi,DeLDeRGhi16. In particular, we perform a new strategy for the proof of the rectifiability of the minimal set, based on the new anisotropic counterpart of the Allard rectifiability theorem proved by the authors in \citeDePDeRGhi2. As a consequence we provide a new proof of Reifenberg existence theorem.
  • PDF
    Totally Asymmetric Simple Exclusion Process (TASEP) on $\mathbb{Z}$ is one of the classical exactly solvable models in the KPZ universality class. We study the "slow bond" model, where TASEP on $\mathbb{Z}$ is imputed with a slow bond at the origin. The slow bond increases the particle density immediately to its left and decreases the particle density immediately to its right. Whether or not this effect is detectable in the macroscopic current started from the step initial condition has attracted much interest over the years and this question was settled recently (Basu, Sidoravicius, Sly (2014)) by showing that the current is reduced even for arbitrarily small strength of the defect. Following non-rigorous physics arguments (Janowsky, Lebowitz (1992, 1994)) and some unpublished works by Bramson, a conjectural description of properties of invariant measures of TASEP with a slow bond at the origin was provided in Liggett's 1999 book. We establish Liggett's conjectures and in particular show that TASEP with a slow bond at the origin, started from step initial condition, converges in law to an invariant measure that is asymptotically close to product measures with different densities far away from the origin towards left and right. Our proof exploits the correspondence between TASEP and the last passage percolation on $\mathbb{Z}^2$ with exponential weights and uses the understanding of geometry of maximal paths in those models.
  • PDF
    In the present work we are going to give a formal exposition of the ribbon graphs topic based on notes of Labourie \citeLab, since is difficult to find as such in the literature.
  • PDF
    We give lower bounds for the Gordian distance and the unknotting number of handlebody-knots by using Alexander biquandle colorings. We construct handlebody-knots with Gordian distance $n$ and unknotting number $n$ for any positive integer $n$.
  • PDF
    In this paper we study the moduli space of properly Alexandrov-embedded, minimal annuli in $\mathbb{H}^2 \times \mathbb{R}$ with horizontal ends. We say that the ends are horizontal when they are graphs of $\mathcal{C}^{2, \alpha}$ functions over $\partial_\infty \mathbb{H}^2$. Contrary to expectation, we show that one can not fully prescribe the two boundary curves at infinity, but rather, one can prescribe the bottom curve, but the top curve only up to a translation and a tilt, along with the position of the neck and the vertical flux of the annulus. We also prove general existence theorems for minimal annuli with discrete groups of symmetries.
  • PDF
    Partition functions arise in statistical physics and probability theory as the normalizing constant of Gibbs measures and in combinatorics and graph theory as graph polynomials. For instance the partition functions of the hard-core model and monomer-dimer model are the independence and matching polynomials respectively. We show how stability results follow naturally from the recently developed occupancy method for maximizing and minimizing physical observables over classes of regular graphs, and then show these stability results can be used to obtain tight extremal bounds on the individual coefficients of the corresponding partition functions. As applications, we prove new bounds on the number of independent sets and matchings of a given size in regular graphs. For large enough graphs and almost all sizes, the bounds are tight and confirm the Upper Matching Conjecture of Friedland, Krop, and Markström and a conjecture of Kahn on independent sets for a wide range of parameters. Additionally we prove tight bounds on the number of $q$-colorings of cubic graphs with a given number of monochromatic edges, and tight bounds on the number of independent sets of a given size in cubic graphs of girth at least $5$.
  • PDF
    Foldable paper constructions known as flexagons have been studied since 1939. In this paper we review the construction of hexagonal flexagons (hexaflexagons) and compute the number of distinct hexaflexagons with n faces.
  • PDF
    We revisit closed-loop performance guarantees for Model Predictive Control in the deterministic and stochastic cases, which extend to novel performance results applicable to receding horizon control of Partially Observable Markov Decision Processes. While performance guarantees similar to those achievable in deterministic Model Predictive Control can be obtained even in the stochastic case, the presumed stochastic optimal control law is intractable to obtain in practice. However, this intractability relaxes for a particular instance of stochastic systems, namely Partially Observable Markov Decision Processes, provided reasonable problem dimensions are taken. This motivates extending available performance guarantees to this particular class of systems, which may also be used to approximate general nonlinear dynamics via gridding of state, observation, and control spaces. We demonstrate applicability of the novel closed-loop performance results on a particular example in healthcare decision making, which relies explicitly on the duality of the control decisions associated with Stochastic Optimal Control in weighing appropriate appointment times, diagnostic tests, and medical intervention for treatment of a disease modeled by a Markov Chain.
  • PDF
    Output-Feedback Stochastic Model Predictive Control based on Stochastic Optimal Control for nonlinear systems is computationally intractable because of the need to solve a Finite Horizon Stochastic Optimal Control Problem. However, solving this problem leads to an optimal probing nature of the resulting control law, called dual control, which trades off benefits of exploration and exploitation. In practice, intractability of Stochastic Model Predictive Control is typically overcome by replacement of the underlying Stochastic Optimal Control problem by more amenable approximate surrogate problems, which however come at a loss of the optimal probing nature of the control signals. While probing can be superimposed in some approaches, this is done sub-optimally. In this paper, we examine approximation of the system dynamics by a Partially Observable Markov Decision Process with its own Finite Horizon Stochastic Optimal Control Problem, which can be solved for an optimal control policy, implemented in receding horizon fashion. This procedure enables maintaining probing in the control actions. We further discuss a numerical example in healthcare decision making, highlighting the duality in stochastic optimal receding horizon control.
  • PDF
    The paper discusses stably trivial torsors for spin and orthogonal groups over smooth affine schemes over infinite perfect fields of characteristic unequal to 2. We give a complete description of all the invariants relevant for the classification of such objects over schemes of dimension at most $3$, along with many examples. The results are based on the $\mathbb{A}^1$-representability theorem for torsors and transfer of known computations of $\mathbb{A}^1$-homotopy sheaves along the sporadic isomorphisms to spin groups.
  • PDF
    We study the flow of the special linear group over the p-adics, acting on its space of types. We determine the minimal subflows as well as the Ellis group.
  • PDF
    This paper considers the design of the beamformers for a multiple-input single-output (MISO) downlink system that seeks to mitigate the impact of the imperfections in the channel state information (CSI) that is available at the base station (BS). The goal of the design is to minimize the outage probability of specified signal-to-interference-and-noise ratio (SINR) targets, while satisfying per-antenna power constraints (PAPCs), and to do so at a low computational cost. Based on insights from the offset maximization technique for robust beamforming, and observations regarding the structure of the optimality conditions, low-complexity iterative algorithms that involve the evaluation of closed-form expressions are developed. To further reduce the computational cost, algorithms are developed for per-antenna power-constrained variants of the zero-forcing (ZF) and maximum ratio transmission (MRT) beamforming directions. In the MRT case, our low-complexity version for systems with a large number of antennas may be of independent interest. The proposed algorithms are extended to systems with both PAPCs and a total power constraint. Simulation results show that the proposed robust designs can provide substantial gains in the outage probability while satisfying the PAPCs.
  • PDF
    An alternating sign matrix, or ASM, is a $(0, \pm 1)$-matrix where the nonzero entries in each row and column alternate in sign. We generalize this notion to hypermatrices: an $n\times n\times n$ hypermatrix $A=[a_{ijk}]$ is an \em alternating sign hypermatrix, or ASHM, if each of its planes, obtained by fixing one of the three indices, is an ASM. Several results concerning ASHMs are shown, such as finding the maximum number of nonzeros of an $n\times n\times n$ ASHM, and properties related to Latin squares. Moreover, we investigate completion problems, in which one asks if a subhypermatrix can be completed (extended) into an ASHM. We show several theorems of this type.
  • PDF
    In this paper, we investigate secure transmission over the large-scale multiple-antenna wiretap channel with finite alphabet inputs. First, we investigate the case where instantaneous channel state information (CSI) of the eavesdropper is known at the transmitter. We show analytically that a generalized singular value decomposition (GSVD) based design, which is optimal for Gaussian inputs, may exhibit a severe performance loss for finite alphabet inputs in the high signal-to-noise ratio (SNR) regime. In light of this, we propose a novel Per-Group-GSVD (PG-GSVD) design which can effectively compensate the performance loss caused by the GSVD design. More importantly, the computational complexity of the PG-GSVD design is by orders of magnitude lower than that of the existing design for finite alphabet inputs in [1] while the resulting performance loss is minimal. Then, we extend the PG-GSVD design to the case where only statistical CSI of the eavesdropper is available at the transmitter. Numerical results indicate that the proposed PG-GSVD design can be efficiently implemented in large-scale multiple-antenna systems and achieves significant performance gains compared to the GSVD design.
  • PDF
    The existence of a countably compact group without non-trivial convergent sequences in ZFC alone is a major open problem in topological group theory. We give a ZFC example of a Boolean topological group G without non-trivial convergent sequences having the following "selective" compactness property: For each free ultrafilter p on N and every sequence U_n:n in N of non-empty open subsets of G one can choose a point x_n in U_n for all n in such a way that the resulting sequence x_n:n in N has a p-limit in G, that is, n in N: x_n in V belongs to p for every neighbourhood V of x in G. In particular, G is selectively pseudocompact (strongly pseudocompact) but not selectively sequentially pseudocompact. This answers a question of Dorantes-Aldama and the first author. As a by-product, we show that the free precompact Boolean group over any disjoint sum of maximal countable spaces contains no infinite compact subsets.
  • PDF
    Fintushel and Stern showed that the Brieskorn sphere $\Sigma(2,3,7)$ bounds a rational homology ball, while its non-trivial Rokhlin invariant obstructs it from bounding an integral homology ball. It is known that their argument can be modified to show that the figure-eight knot is rationally slice, and we use this fact to provide the first additional examples of Brieskorn spheres that bound rational homology balls but not integral homology balls: the families $\Sigma(2,4n+1,12n+5)$ and $\Sigma(3,3n+1,12n+5)$ for $n$ odd. We also provide handlebody diagrams for a rational homology ball containing a rationally slice disk for the figure-eight knot, as well as for a rational homology ball bounded by $\Sigma(2,3,7)$. These handle diagrams necessarily contain 3-handles.
  • PDF
    The combined work of Guaraco, Hutchinson, Tonegawa and Wickramasekera has recently produced a new proof of the classical theorem that any closed Riemannian manifold of dimension $n + 1 \geq 3$ contains a minimal hypersurface with a singular set of Hausdorff dimension at most $n-7$. This proof avoids the Almgren--Pitts geometric min-max procedure for the area functional that was instrumental in the original proof, and is instead based on a considerably simpler PDE min-max construction of critical points of the Allen--Cahn functional. Here we prove a spectral lower bound for the hypersurfaces arising from this construction. This directly implies an upper bound for the Morse index of the hypersurface in terms of the indices of the critical points, provided it is two-sided. In particular, two-sided hypersurfaces arising from Guaraco's construction have Morse index at most $1$. Finally, we point out by an elementary inductive argument how the regularity of the hypersurface follows from the corresponding result in the stable case.
  • PDF
    We continue our investigation of integral spans of tight frames in Euclidean spaces. In a previous paper, we considered the case of an equiangular tight frame (ETF), proving that if its integral span is a lattice then the frame must be rational, but overlooking a simple argument in the reverse direction. Thus our first result here is that the integral span of an ETF is a lattice if and only if the frame is rational. Further, we discuss conditions under which such lattices are eutactic and perfect and, consequently, are local maxima of the packing density function in the dimension of their span. In particular, the unit (276, 23) equiangular tight frame is shown to be eutactic and perfect. More general tight frames and their norm-forms are considered as well, and definitive results are obtained in dimensions two and three.
  • PDF
    This work dynamically classifies a 9-parametric family of birational maps f : C2 -> C2. From the sequence of the degrees dn of the iterates of f, we find the dynamical degree delta(f) of f. We identify when dn grows periodically, linearly, quadratically or exponentially. The considered family includes the birational maps studied by Bedford and Kim in [4] as one of its subfamilies.
  • PDF
    The Kundu-Eckhaus equation is a nonlinear partial differential equation which seems in the quantum field theory, weakly nonlinear dispersive water waves and nonlinear optics. In spite of its importance, exact solution to this nonlinear equation are rarely found in literature. In this work, we solve this equation and present a new approach to obtain the solution by means of the combined use of the Adomian Decomposition Method and the Laplace Transform (LADM). Besides, we compare the behaviour of the solutions obtained with the only exact solutions given in the literature through fractional calculus. Moreover, it is shown that the proposed method is direct, effective and can be used for many other nonlinear evolution equations in mathematical physics.
  • PDF
    The proofs of Oka's Coherence Theorems are based on Weierstrass' Preparation (division) Theorem. Here we observe that a Weak Coherence of Oka proved without Weierstrass' Preparation (division) Theorem, but only with \textitpower series expansions is sufficient to prove Oka's Jôku-Ikô and hence Cousin I, II, holomorphic extensions, and Levi's Problem, as far as the domain spaces are non-singular. The proof of the Weak Coherence of Oka is almost of linear algebra. We will present some new or simplified arguments in the proofs.
  • PDF
    Cauchy's sum theorem is a prototype of what is today a basic result on the convergence of a series of functions in undergraduate analysis. We seek to interpret Cauchy's proof, and discuss the related epistemological questions involved in comparing distinct interpretive paradigms. Cauchy's proof is often interpreted in the modern framework of a Weierstrassian paradigm. We analyze Cauchy's proof closely and show that it finds closer proxies in a different modern framework. Keywords: Cauchy's infinitesimal; sum theorem; quantifier alternation; uniform convergence; foundational paradigms.
  • PDF
    Using diagrammatic techniques, we provide an explicit proof of the single ring theorem, including the recent extension for the correlation function built out of left and right eigenvectors of a non-Hermitian matrix. We present the operational formalism allowing to map mutually the two distinct areas of free random variables: Hermitian positive definite operators and non-normal R-diagonal operators, realized as the large size limit of biunitarily invariant random matrices.
  • PDF
    Given one metric measure space $X$ satisfying a linear Brunn-Minkowski inequality, and a second one $Y$ satisfying a Brunn-Minkowski inequality with exponent $p\ge -1$, we prove that the product $X\times Y$ with the standard product distance and measure satisfies a Brunn-Minkowski inequality of order $1/(1+p^{-1})$ under mild conditions on the measures and the assumption that the distances are strictly intrinsic. The same result holds when we consider restricted classes of sets. We also prove that a linear Brunn-Minkowski inequality is obtained in $X\times Y$ when $Y$ satisfies a Prékopa-Leindler inequality. In particular, we show that the classical Brunn-Minkowski inequality holds for any pair of weakly unconditional sets in $\mathbb{R}^n$ (i.e., those containing the projection of every point in the set onto every coordinate subspace) when we consider the standard distance and the product measure of $n$ one-dimensional real measures with positively decreasing densities. This yields an improvement of the class of sets satisfying the Gaussian Brunn-Minkowski inequality. Furthermore, associated isoperimetric inequalities as well as recently obtained Brunn-Minkowski's inequalities are derived from our results.
  • PDF
    Let $\mathcal{B}$ denote a set of bicolorings of $[n]$, where each bicoloring is a mapping of the points in $[n]$ to $\{-1,+1\}$. For each $B \in \mathcal{B}$, let $Y_B=(B(1),\ldots,B(n))$. For each $A \subseteq [n]$, let $X_A \in \{0,1\}^n$ denote the incidence vector of $A$. A non-empty set $A$ is said to be an `unbiased representative' for a bicoloring $B \in \mathcal{B}$ if $\left\langle X_A,Y_B\right\rangle =0$. Given a set $\mathcal{B}$ of bicolorings, we study the minimum cardinality of a family $\mathcal{A}$ consisting of subsets of $[n]$ such that every bicoloring in $\mathcal{B}$ has an unbiased representative in $\mathcal{A}$.
  • PDF
    One of the most intriguing problems, in $q$-analogs of designs, is the existence question of an infinite family of $q$-analog of Steiner systems, known also as $q$-Steiner systems, (spreads not included) in general, and the existence question for the $q$-analog of the Fano plane, known also as the $q$-Fano plane, in particular. These questions are in the front line of open problems in block design. There was a common belief and a conjecture that such structures do not exist. Only recently, $q$-Steiner systems were found for one set of parameters. In this paper, a definition for the $q$-analog of the residual design is presented. This new definition is different from previous known definition, but its properties reflect better the $q$-analog properties. The existence of a design with the parameters of the residual $q$-Steiner system in general and the residual $q$-Fano plane in particular are examined. We prove the existence of the residual $q$-Fano plane for all $q$, where $q$ is a prime power. The constructed structure is just one step from a construction of a $q$-Fano plane.
  • PDF
    Let $Q$ be a nondegenerate quadratic form on a vector space $V$ of even dimension $n$ over a number field $F$. Via the circle method or automorphic methods one can give good estimates for smoothed sums over the number of zeros of the quadratic form whose coordinates are of size at most $X$ (properly interpreted). For example, when $F=\mathbb{Q}$ and $\dim V>4$ Heath-Brown has given an asymptotic of the form \beginalign \labelHB:esti c_1X^n-2+O_Q,\varepsilon,f(X^n/2+\varepsilon) \endalign for any $\varepsilon>0$. Here $c_1 \in \mathbb{C}$ and $f \in \mathcal{S}(V(\mathbb{R}))$ is a smoothing function. We refine Heath-Brown's work to give an asymptotic of the form $$ c_1X^n-2+c_2X^n/2+O_Q,\varepsilon,f(X^n/2+\varepsilon-1) $$ over any number field. Here $c_2 \in \mathbb{C}$. Interestingly the secondary term $c_2$ is the sum of a rapidly decreasing function on $V(\mathbb{R})$ over the zeros of $Q^{\vee}$, the form whose matrix is inverse to the matrix of $Q$. We also prove analogous results in the boundary case $n=4$, generalizing and refining Heath-Brown's work in the case $F=\mathbb{Q}$.
  • PDF
    We propose an optimal transportation aproach to price European options under the Stein-Stein stochastic volatility model by using the flow that transports the set of particles from prior to the posterior distribution. We also propose to direct the flow to a rarely corners of the state space by using a mutation and reweighing algorithm. We demonstrate the efficiency of our approach on a simple example for which the closed form formula is available. This methods shows the advantage of having low variance and bias and contrasts to other filtering schemes recently developed in signal-processing literature, including particle filter technique.
  • PDF
    A generalisation of the Lie symmetry method is applied to classify a coupled system of reaction-diffusion equations wherein the nonlinearities involve arbitrary functions in the limit case in which one equation of the pair is quasi-steady but the other not. A complete Lie symmetry classification, including a number of the cases characterised being unlikely to be identified purely by intuition, is obtained. Notably, in addition to the symmetry analysis of the PDEs themselves, the approach is extended to allow the derivation of exact solutions to specific moving-boundary problems motivated by biological applications tumour growth). Graphical representations of the solutions are provided and biological interpretation addressed briefly. The results are generalised on multi-dimensional case under assumption of radially symmetrical shape of the tumour.
  • PDF
    We study a lossy source coding problem for a memoryless remote source. The source data is broadcast over an arbitrarily varying channel (AVC) controlled by an adversary. One output of the AVC is received as input at the encoder, and another output is received as side information at the decoder. The adversary is assumed to know the source data non-causally, and can employ randomized jamming strategies arbitrarily correlated to the source data. The decoder reconstructs the source data from the encoded message and the side information. We prove upper and lower bounds on the adversarial rate distortion function for the source under randomized coding. Furthermore, we present some interesting special cases of our general setup where the above bounds coincide, and thus, provide their complete rate distortion function characterization.
  • PDF
    We give a formula of the connected component decomposition of the Alexander quandle: $\mathbb{Z}[t^{\pm1}]/(f_1(t),\ldots, f_k(t))=\bigsqcup^{a-1}_{i=0}\mathrm{Orb}(i)$, where $a=\gcd (f_1(1),\ldots, f_k(1))$. We show that the connected component $\mathrm{Orb}(i)$ is isomorphic to $\mathbb{Z}[t^{\pm1}]/J$ with an explicit ideal $J$. By using this, we see how a quandle is decomposed into connected components for some Alexander quandles. We introduce a decomposition of a quandle into the disjoint union of maximal connected subquandles. In some cases, this decomposition is obtained by iterating a connected component decomposition. We also discuss the maximal connected sub-multiple conjugation quandle decomposition.
  • PDF
    A pseudocircle is a simple closed curve on some surface. Arrangements of pseudocircles were introduced by Grünbaum, who defined them as collections of pseudocircles that pairwise intersect in exactly two points, at which they cross. There are several variations on this notion in the literature, one of which requires that no three pseudocircles have a point in common. Working under this definition, Ortner proved that an arrangement of pseudocircles is embeddable into the sphere if and only if all of its subarrangements of size at most $4$ are embeddable into the sphere. Ortner asked if an analogous result held for embeddability into a compact orientable surface $\Sigma_g$ of genus $g>0$. In this paper we answer this question, under an even more general definition of an arrangement, in which the pseudocircles in the collection are not required to intersect each other, or that the intersections are crossings: it suffices to have one pseudocircle that intersects all other pseudocircles in the collection. We show that under this more general notion, an arrangement of pseudocircles is embeddable into $\Sigma_g$ if and only if all of its subarrangements of size at most $4g+5$ are embeddable into $\Sigma_g$, and that this can be improved to $4g+4$ under the concept of an arrangement used by Ortner. Our framework also allows us to generalize this result to arrangements of other objects, such as arcs.
  • PDF
    Nonlinear controlled plants with Bogdanov-Takens singularity may experience surprising changes in their number of equilibria, limit cycles and/or their stability types when the controllers slightly vary in the vicinity of critical parameter varieties. Each such a change is called a local bifurcation. We are concerned with the local bifurcation control of the generalized cusp case of Bogdanov--Takens singularity. In this direction, we derive novel results with regards to parametric normal forms of the generalized cusp plants. An orbital normal form and a truncated state-feedback linear controller normal form for this family are also provided. We suggest effective nonlinear bifurcation control law designs for precisely locating and accurately controlling many different types of bifurcations for two measurable plants. The first is a general quadratic plant with a possible multi-input linear controller while the second is a Z_2-equivariant general plant with possible multi-input linear (preserving Z_2-symmetry) and quadratic (symmetry-breaking) controllers. The bifurcations include from primary to quinary bifurcations of either of the following types: saddle-node and pitchfork of equilibria, Z_2-equivariant bifurcations of multiple limit cycles through saddle-node, Hopf, homoclinic, heteroclinic and saddle-connections, and finally their one-parameter symmetry breaking bifurcations. We further propose a systematic approach for efficient treatment of tracking and regulating engineering problems. Our approach also facilitates a systematic derivation of a local state-feedback normal form linearization modulo arbitrary high degrees. These are applicable to the cases uncontrollable by the classical input-state feedback linearization and back-stepping methods in nonlinear control theory. Symbolic implementations and numerical simulations confirm our theoretical results and accurate predictions.
  • PDF
    We exhibit a non-varying phenomenon for the counting problem of cylinders, weighted by their area, passing through two marked (regular) Weierstrass points of a translation surface in a hyperelliptic connected component $\mathcal{H}^{hyp}(2g-2)$ or $\mathcal{H}^{hyp}(g-1,g-1)$, $g > 1$. As an application, we obtain the non-varying phenomenon for the counting problem of (weighted) periodic trajectories on the classical wind-tree model, a billiard in the plane endowed with $\mathbb{Z}^2$-periodically located identical rectangular obstacles.
  • PDF
    In this note we aim to characterize the cylindrical Wigner measures associated to regular quantum states in the Weyl C*-algebra of canonical commutation relations. In particular, we provide conditions at the quantum level sufficient to prove the concentration of all the corresponding cylindrical Wigner measures as Radon measures on suitable topological vector spaces. The analysis is motivated by variational and dynamical problems in the semiclassical study of bosonic quantum field theories.
  • PDF
    We prove that the ground space projections of a subspace of energy operators in a matrix *-algebra are the greatest projections of the algebra under certain operator cone constraints. The lattice of ground space projections being coatomistic, we also discuss its maximal elements as building blocks. We demonstrate the results with (commutative) two-local three-bit Hamiltonians. We expect the variation principle to be useful also for non-commutative Hamiltonians.
  • PDF
    A balancing domain decomposition by constraints (BDDC) algorithm with adaptive primal constraints in variational form is introduced and analyzed for high-order mortar discretization of two-dimensional elliptic problems with high varying and random coefficients. Some vector-valued auxiliary spaces and operators with essential properties are defined to describe the variational algorithm, and the coarse space is formed by using a transformation operator on each interface. Compared with the adaptive BDDC algorithms for conforming Galerkin approximations, our algorithm is more simple, because there is not any continuity constraints at subdomain vertices in the mortar method involved in this paper. The condition number of the preconditioned system is proved to be bounded above by a user-defined tolerance and a constant which is dependent on the maximum number of interfaces per subdomain, and independent of the mesh size and the contrast of the given coefficients. Numerical results show the robustness and efficiency of the algorithm for various model problems.
  • PDF
    We introduce in this work the notion of the category of pure $\mathbf{E}$-Motives, where $\mathbf{E}$ is a motivic strict ring spectrum and construct twisted $\mathbf{E}$-cohomology by using six functors formalism of J. Ayoub. In particular, we construct the category of pure Chow-Witt motives $CHW(k)_{\mathbb{Q}}$ over a field $k$ and show that this category admits a fully faithful embedding into the geometric stable $\mathbb{A}^1$-derived category $D_{\mathbb{A}^1,gm}(k)_{\mathbb{Q}}$.
  • PDF
    We give a unified approach to constructing quaternary sequences with even period and low autocorrelation from pairs of binary sequences with even period and optimal autocorrelation. We obtain several families of balanced and almost balanced quaternary sequences with low autocorrelation using this approach, as well as investigate their linear complexity.

Recent comments

Zoltán Zimborás Apr 18 2017 09:47 UTC

Great note. I real like the two end-sentences: "Of course, any given new approach to a hard and extensively studied problem has a very low probability to lead to a direct solution (some popular accounts may not have emphasized this to the degree we would have preferred). But arguably, this makes the

...(continued)
Jalex Stark Apr 06 2017 22:46 UTC

However, one should note that I_3322 may be able to do something that this paper doesn't. William's work leaves open the question of whether there are games with infinite-dimensional tensor product strategies but no finite-dimensional ones. Some of us might expect that I_3322 has this property.

Laura Mančinska Mar 28 2017 13:09 UTC

Great result!

For those familiar with I_3322, William here gives an example of a nonlocal game exhibiting a behaviour that many of us suspected (but couldn't prove) to be possessed by I_3322.

gae spedalieri Mar 13 2017 14:13 UTC

1) Sorry but this is false.

1a) That analysis is specifically for reducing QECC protocol to an entanglement distillation protocol over certain class of discrete variable channels. Exactly as in BDSW96. Task of the protocol is changed in the reduction.

1b) The simulation is not via a general LOCC b

...(continued)
Siddhartha Das Mar 13 2017 13:22 UTC

We feel that we have cited and credited previous works appropriately in our paper. To clarify:

1) The LOCC simulation of a channel and the corresponding adaptive reduction can be found worked out in full generality in the 2012 Master's thesis of Muller-Hermes. We have cited the original paper BD

...(continued)
gae spedalieri Mar 13 2017 08:56 UTC

This is one of those papers where the contribution of previous literature is omitted and not fairly represented.

1- the LOCC simulation of quantum channels (not necessarily teleportation based) and the corresponding general reduction of adaptive protocols was developed in PLOB15 (https://arxiv.org/

...(continued)
Andrey Karchevsky Feb 17 2017 09:51 UTC

Dear Authors,

This is in reference of your preprint arxiv 1702.0638.

Above all I must say that I am puzzled with the level of publicity your work has got at http://www.nature.com/news/long-awaited-mathematics-proof-could-help-scan-earth-s-innards-1.21439. Is this a new way for mathematicians t

...(continued)
Robert Raussendorf Jan 24 2017 22:29 UTC

Regarding Mark's above comment on the role of the stabilizer states: Yes, all previous works on the subject have used the stabilizer states and Clifford gates as the classical backbone. This is due to the Gottesman-Knill theorem and related results. But is it a given that the free sector in quantum

...(continued)
Planat Jan 24 2017 13:09 UTC

Are you sure? Since we do not propose a conjecture, there is nothing wrong. A class of strange states underlie the pentagons in question. The motivation is to put the magic of computation in the permutation frame, one needs more work to check its relevance.

Mark Howard Jan 24 2017 09:59 UTC

It seems interesting at first sight, but after reading it the motivation is very muddled. It boils down to finding pentagons (which enable KCBS-style proofs of contextuality) within sets of projectors, some of which are stabilizer states and some of which are non-stabilizer states (called magic stat

...(continued)