Search

We introduce the triangulant of two matrices, and relate it to the existence of orthogonal eigenvectors. We also use it for a new characterization of mutually unbiased bases. Generalizing the notion, we introduce higher order triangulants of two matrices, and relate them to the existence of nontrivially intersecting invariant subspaces of complementary dimensions., Comment: 16 pages

Integral representations of quantum relative entropy, and of the directional second and higher order derivatives of von Neumann entropy, are established, and used to give simple proofs of fundamental, known data processing inequalities: the Holevo bound on the quantity of information transmitted by a quantum communication channel, and, much more generally, the monotonicity of quantum relative entropy under trace-preserving positive linear maps -- complete positivity of the map need not be assumed. The latter result was first proved by M\"uller-Hermes and Reeb, based on work of Beigi. For a simple application of such monotonicities, we consider any `divergence' that is non-increasing under quantum measurements, such as the concavity of von Neumann entropy, or various known quantum divergences. An elegant argument due to Hiai, Ohya, and Tsukada is used to show that the infimum of such a `divergence' on pairs of quantum states with prescribed trace distance is the same as the corresponding infimum on pairs of binary classical states. Applications of the new integral formulae to the general probabilistic model of information theory, and a related integral formula for the classical R\'enyi divergence, are also discussed., Comment: 16 pages. Accepted to Quantum

For a classical channel, neither the Shannon capacity, nor the sum of conditional probabilities corresponding to the cases of successful transmission can be increased by the use of shared entanglement, or, more generally, a non-signaling resource. Yet, perhaps somewhat counterintuitively, entanglement assistance can help and actually elevate the chances of success even in a one-way communicational task that is to be completed by a single-shot use of a noiseless classical channel. To quantify the help that a non-signaling resource provides to a noiseless classical channel, one might ask how many extra letters should be added to the alphabet of the channel in order to perform equally well without the specified non-signaling resource. As was observed by Cubitt, Leung, Matthews, and Winter, there is no upper bound on the number of extra letters required for substituting the assistance of a general non-signaling resource to a noiseless one-bit classical channel. In contrast, here we prove that if this resource is a bipartite quantum system in a maximally entangled state, then an extra classical bit always suffices as a replacement., Comment: This is the version accepted to the journal Quantum

We investigate whether certain non-classical communication channels can be simulated by a classical channel with a given number of states and a given `amount' of noise. It is proved that any noisy quantum channel can be simulated by a corresponding classical channel with `the same amount' of noise. Classical simulations of general probabilistic channels are also studied., Comment: 16 pages. This is the version to appear in Quantum. Minor changes requested by the referee have been made

Let $p$ be a fixed prime, and let $v(a)$ stand for the exponent of $p$ in the prime factorization of the integer $a$. Let $f$ and $g$ be two monic polynomials with integer coefficients and nonzero resultant $r$. Write $S$ for the maximum of $v(\gcd (f(n), g(n)))$ over all integers $n$. It is known that $S \le v(r)$. We give various lower and upper bounds for the least possible value of $v(r)-S$ provided that a given power $p^s$ divides both $f(n)$ and $g(n)$ for all $n$. In particular, the least possible value is $ps^2-s$ for $s\le p$ and is asymptotically $(p-1)s^2$ for large $s$., Comment: 12 pages

We show that if two monic polynomials with integer coefficients have square-free resultant, then all positive divisors of the resultant arise as the greatest common divisor of the values of the two polynomials at a suitable integer., Comment: 6 pages

We propose a notion of graph convergence that interpolates between the Benjamini--Schramm convergence of bounded degree graphs and the dense graph convergence developed by L\'aszl\'o Lov\'asz and his coauthors. We prove that spectra of graphs, and also some important graph parameters such as numbers of colorings or matchings, behave well in convergent graph sequences. Special attention is given to graph sequences of large essential girth, for which asymptotics of coloring numbers are explicitly calculated. We also treat numbers of matchings in approximately regular graphs. We introduce tentative limit objects that we call graphonings because they are common generalizations of graphons and graphings. Special forms of these, called Hausdorff and Euclidean graphonings, involve geometric measure theory. We construct Euclidean graphonings that provide limits of hypercubes and of finite projective planes, and, more generally, of a wide class of regular sequences of large essential girth. For any convergent sequence of large essential girth, we construct weaker limit objects: an involution invariant probability measure on the sub-Markov space of consistent measure sequences (this is unique), or an acyclic reversible sub-Markov kernel on a probability space (non-unique). We also pose some open problems., Comment: 41 pages. Minor errors have been corrected

We determine the automorphisms and the continuous endomorphisms of the Einstein gyrogroup in arbitrary dimension. This generalizes a recent result of Lajos Moln\'ar and D\'aniel Virosztek, who have determined the continuous endomorphisms in the three-dimensional case., Comment: 4 pages

In this short note we observe that recent results of Abert and Hubai and of Csikvari and Frenkel about Benjamini--Schramm continuity of the holomorphic moments of the roots of the chromatic polynomial extend to the theory of dense graph sequences. We offer a number of problems and conjectures motivated by this observation., Comment: 9 pages

We determine minimal Cayley--Hamilton and Capelli identities for matrices over a Grassmann algebra of finite rank. For minimal standard identities, we give lower and upper bounds on the degree. These results improve on upper bounds given by L.\ M\'arki, J.\ Meyer, J.\ Szigeti, and L.\ van Wyk in a recent paper., Comment: 9 pages

We introduce the matching measure of a finite graph as the uniform distribution on the roots of the matching polynomial of the graph. We analyze the asymptotic behavior of the matching measure for graph sequences with bounded degree. A graph parameter is said to be estimable if it converges along every Benjamini-Schramm convergent sparse graph sequence. We prove that the normalized logarithm of the number of matchings is estimable. We also show that the analogous statement for perfect matchings already fails for d-regular bipartite graphs for any fixed d at least 3. The latter result relies on analyzing the probability that a randomly chosen perfect matching contains a particular edge. However, for any sequence of d-regular bipartite graphs converging to the d-regular tree, we prove that the normalized logarithm of the number of perfect matchings converges. This applies to random d-regular bipartite graphs. We show that the limit equals to the exponent in Schrijver's lower bound on the number of perfect matchings. Our analytic approach also yields a short proof for the Nguyen-Onak (also Elek--Lippner) theorem saying that the matching ratio is estimable. In fact, we prove the slightly stronger result that the independence ratio is estimable for claw-free graphs., Comment: 21 pages. Changes compared to the previous (published) version: In Lemma 4.3, formula (4.3) and its proof have been corrected. As a consequence, the formula for the variance in Theorem 4.5 has been modified

A game is played by a team of two --- say Alice and Bob --- in which the value of a random variable $x$ is revealed to Alice only, who cannot freely communicate with Bob. Instead, she is given a quantum $n$-level system, respectively a classical $n$-state system, which she can put in possession of Bob in any state she wishes. We evaluate how successfully they managed to store and recover the value of $x$ in the used system by requiring Bob to specify a value $z$ and giving a reward of value $ f(x,z)$ to the team. We show that whatever the probability distribution of $x$ and the reward function $f$ are, when using a quantum $n$-level system, the maximum expected reward obtainable with the best possible team strategy is equal to that obtainable with the use of a classical $n$-state system. The proof relies on mixed discriminants of positive matrices and --- perhaps surprisingly --- an application of the Supply--Demand Theorem for bipartite graphs. As a corollary, we get an infinite set of new, dimension dependent inequalities regarding positive operator valued measures and density operators on complex $n$-space. As a further corollary, we see that the greatest value, with respect to a given distribution of $x$, of the mutual information $I(x;z)$ that is obtainable using an $n$-level quantum system equals the analogous maximum for a classical $n$-state system., Comment: 13 pages

Positive polynomials arising from Muirhead's inequality, from classical power mean and elementary symmetric mean inequalities and from Minkowski's inequality can be rewritten as sums of squares., Comment: 8 pages

Recently, M.\ Ab\'ert and T.\ Hubai studied the following problem. The chromatic measure of a finite simple graph is defined to be the uniform distribution on its chromatic roots. Ab\'ert and Hubai proved that for a Benjamini-Schramm convergent sequence of finite graphs, the chromatic measures converge in holomorphic moments. They also showed that the normalized log of the chromatic polynomial converges to a harmonic real function outside a bounded disc. In this paper we generalize their work to a wide class of graph polynomials, namely, multiplicative graph polynomials of bounded exponential type. A special case of our results is that for any fixed complex number $v_0$ the measures arising from the Tutte polynomial $Z_{G_n}(z,v_0)$ converge in holomorphic moments if the sequence $(G_n)$ of finite graphs is Benjamini--Schramm convergent. This answers a question of Ab\'ert and Hubai in the affirmative. Even in the original case of the chromatic polynomial, our proof is considerably simpler., Comment: 22 pages. Minor corrections made

Let $v_1$,..., $v_n$ be $n$ vectors in an inner product space. Can we find a natural number $d$ and positive (semidefinite) complex matrices $A_1$,..., $A_n$ of size $d \times d$ such that ${\rm Tr}(A_kA_l)= $ for all $k,l=1,..., n$? For such matrices to exist, one must have $ \geq 0$ for all $k,l=1,..., n$. We prove that if $n<5$ then this trivial necessary condition is also a sufficient one and find an appropriate example showing that from $n=5$ this is not so --- even if we allowed realizations by positive operators in a von Neumann algebra with a faithful normal tracial state. The fact that the first such example occurs at $n=5$ is similar to what one has in the well-investigated problem of positive factorization of positive (semidefinite) matrices. If the matrix $()$ has a positive factorization, then matrices $A_1$,..., $A_n$ as above exist. However, as we show by a large class of examples constructed with the help of the Clifford algebra, the converse implication is false., Comment: 8 pages

We recall Vere-Jones's definition of the $\alpha$--permanent and describe the connection between the (1/2)--permanent and the hafnian. We establish expansion formulae for the $\alpha$--permanent in terms of partitions of the index set, and we use these to prove Lieb-type inequalities for the $\pm\alpha$--permanent of a positive semi-definite Hermitian $n\times n$ matrix and the $\alpha/2$--permanent of a positive semi-definite real symmetric $n\times n$ matrix if $\alpha$ is a nonnegative integer or $\alpha\ge n-1$. We are unable to settle Shirai's nonnegativity conjecture for $\alpha$--permanents when $\alpha\ge 1$, but we verify it up to the $5\times 5$ case, in addition to recovering and refining some of Shirai's partial results by purely combinatorial proofs., Comment: 9 pages

We prove pfaffian and hafnian versions of Lieb's inequalities on determinants and permanents of positive semi-definite matrices. We use the hafnian inequality to improve the lower bound of R\'ev\'esz and Sarantopoulos on the norm of a product of linear functionals on a real Euclidean space (this subject is sometimes called the `real linear polarization constant' problem)., Comment: 10 pages

We consider fully effective orientation-preserving smooth actions of a given finite group G on smooth, closed, oriented 3-manifolds M. We investigate the relations that necessarily hold between the numbers of fixed points of various non-cyclic subgroups. In Section 2, we show that all such relations are in fact equations mod 2, and we explain how the number of independent equations yields information concerning low-dimensional equivariant cobordism groups. Moreover, we restate a theorem of A. Szucs asserting that under the conditions imposed on a smooth action of G on M as above, the number of G-orbits of points x in M with non-cyclic stabilizer G_x is even, and we prove the result by using arguments of G. Moussong. In Sections 3 and 4, we determine all the equations for non-cyclic subgroups G of SO(3)., Comment: Published by Algebraic and Geometric Topology at http://www.maths.warwick.ac.uk/agt/AGTVol3/agt-3-24.abs.html