Search

We show that the algebra of the coloured rook monoid $R_n^{(r)}$, {\em i.e.} the monoid of $n \times n$ matrices with at most one non-zero entry (an $r$-th root of unity) in each column and row, is the algebra of a finite groupoid, thus is endowed with a $C^*$-algebra structure. This new perspective uncovers the representation theory of these monoid algebras by making manifest their decomposition in irreducible modules.

The character table of the symmetric group $S_n$, of permutations of $n$ objects, is of fundamental interest in theoretical physics, combinatorics as well as computational complexity theory. We investigate the implications of an identity, which has a geometrical interpretation in combinatorial topological field theories, relating the column sum of normalised central characters of $S_n$ to a sum of structure constants of multiplication in the centre of the group algebra of $S_n$. The identity leads to the proof that a combinatorial computation of the column sum belongs to complexity class \shP. The sum of structure constants has an interpretation in terms of the counting of branched covers of the sphere. This allows the identification of a tractable subset of the structure constants related to genus zero covers. We use this subset to prove that the column sum for a conjugacy class labelled by partition $\lambda$ is non-vanishing if and only if the permutations in the conjugacy class are even. This leads to the result that the determination of the vanishing or otherwise of the column sum is in complexity class \pP. The subset gives a positive lower bound on the column sum for any even $ \lambda$. For any disjoint decomposition of $ \lambda$ as $\lambda_1 \sqcup \lambda_2 $ we obtain a lower bound for the column sum at $ \lambda$ in terms of the product of the column sums for $ \lambda_1$ and$\lambda_2$. This can be expressed as a super-additivity property for the logarithms of column sums of normalized characters., Comment: 52 pages + Appendices, 9 Figures

$U(N)^{\otimes r} \otimes O(N)^{\otimes q}$ invariants are constructed by contractions of complex tensors of order $r+q$, also denoted $(r,q)$. These tensors transform under $r$ fundamental representations of the unitary group $U(N)$ and $q$ fundamental representations of the orthogonal group $O(N)$. Therefore, $U(N)^{\otimes r} \otimes O(N)^{\otimes q}$ invariants are tensor model observables endowed with a tensor field of order $(r,q)$. We enumerate these observables using group theoretic formulae, for arbitrary tensor fields of order $(r,q)$. Inspecting lower-order cases reveals that, at order $(1,1)$, the number of invariants corresponds to a number of 2- or 4-ary necklaces that exhibit pattern avoidance, offering insights into enumerative combinatorics. For a general order $(r,q)$, the counting can be interpreted as the partition function of a topological quantum field theory (TQFT) with the symmetric group serving as gauge group. We identify the 2-complex pertaining to the enumeration of the invariants, which in turn defines the TQFT, and establish a correspondence with countings associated with covers of diverse topologies. For $r>1$, the number of invariants matches the number of ($q$-dependent) weighted equivalence classes of branched covers of the 2-sphere with $r$ branched points. At $r=1$, the counting maps to the enumeration of branched covers of the 2-sphere with $q+3$ branched points. The formalism unveils a wide array of novel integer sequences that have not been previously documented. We also provide various codes for running computational experiments., Comment: 49 pages, 9 figures

Machine Learning approaches like clustering methods deal with massive datasets that present an increasing challenge. We devise parallel algorithms to compute the Multi-Slice Clustering (MSC) for 3rd-order tensors. The MSC method is based on spectral analysis of the tensor slices and works independently on each tensor mode. Such features fit well in the parallel paradigm via a distributed memory system. We show that our parallel scheme outperforms sequential computing and allows for the scalability of the MSC method.

Field theories with combinatorial non-local interactions such as tensor invariants are interesting candidates for describing a phase transition from discrete quantum-gravitational to continuum geometry. In the so-called cyclic-melonic potential approximation of a tensorial field theory on the $r$-dimensional torus it was recently shown using functional renormalization group techniques that no such phase transition to a condensate phase with a tentative continuum geometric interpretation is possible. Here, keeping the same approximation, we show how to overcome this limitation amending the theory by local degrees freedom on $\mathbb{R}^d$. We find that the effective $r-1$ dimensions of the torus part dynamically vanish along the renormalization group flow while the $d$ local dimensions persist up to small momentum scales. Consequently, for $d>2$ one can find a phase structure allowing also for phase transitions., Comment: 25+4 pages, 5 figures

We define the computational task of detecting projectors in finite dimensional associative algebras with a combinatorial basis, labelled by representation theory data, using combinatorial central elements in the algebra. In the first example, the projectors belong to the centre of a symmetric group algebra and are labelled by Young diagrams with a fixed number of boxes $n$. We describe a quantum algorithm for the task based on quantum phase estimation (QPE) and obtain estimates of the complexity as a function of $n$. We compare to a classical algorithm related to the projector identification problem by the AdS/CFT correspondence. This gives a concrete proof of concept for classical/quantum comparisons of the complexity of a detection task, based in holographic correspondences. A second example involves projectors labelled by triples of Young diagrams, all having $n$ boxes, with non-vanishing Kronecker coefficient. The task takes as input the projector, and consists of identifying the triple of Young diagrams. In both of the above cases the standard QPE complexities are polynomial in $n$. A third example of quantum projector detection involves projectors labelled by a triple of Young diagrams, with $m,n$ and $m+n$ boxes respectively, such that the associated Littlewood-Richardson coefficient is non-zero. The projector detection task is to identify the triple of Young diagrams associated with the projector which is given as input. This is motivated by a two-matrix model, related via the AdS/CFT correspondence, to systems of strings attached to giant gravitons. The QPE complexity in this case is polynomial in $m$ and $n$., Comment: 38 pages (including Appendices) ; 2 figures

Enhanced tensor field theories (eTFT) have dominant graphs that differ from the melonic diagrams of conventional tensor field theories. They therefore describe pertinent candidates to escape the so-called branched polymer phase, the universal geometry found for tensor models. For generic order $d$ of the tensor field, we compute the perturbative $\beta$-functions at one-loop of two just-renormalizable quartic eTFT coined by $+$ or $\times$, depending on their vertex weights. The models $+$ has two quartic coupling constants $(\lambda, \lambda_{+})$, and two 2-point couplings(mass, $Z_a$). Meanwhile, the model $\times$ has two quartic coupling constants $(\lambda, \lambda_{\times})$ and three 2-point couplings (mass, $Z_a$, $Z_{2a}$). At all orders, both models have a constant wave function renormalization: $Z=1$ and therefore no anomalous dimension. Despite such peculiar behavior, both models acquire nontrivial radiative corrections for the coupling constants. The RG flow of the model $+$ exhibits a particular asymptotic safety: $\lambda_{+}$ is marginal without corrections thus is a fixed point of arbitrary constant value. All remaining couplings determine relevant directions and get suppressed in the UV. Concerning the model $\times$, $\lambda_{\times}$ is marginal and again a fixed point (arbitrary constant value), $\lambda$, $\mu$ and $Z_a$ are all relevant couplings and flow to 0. Meanwhile $Z_{2a}$ is a marginal coupling and becomes a linear function of the time scale. This model can neither be called asymptotically safe or free., Comment: 48 pages, 20 figures, scaling dimensions corrected, some statements corrected, typos fixed

Several methods for triclustering three-dimensional data require the cluster size or the number of clusters in each dimension to be specified. To address this issue, the Multi-Slice Clustering (MSC) for 3-order tensor finds signal slices that lie in a low dimensional subspace for a rank-one tensor dataset in order to find a cluster based on the threshold similarity. We propose an extension algorithm called MSC-DBSCAN to extract the different clusters of slices that lie in the different subspaces from the data if the dataset is a sum of r rank-one tensor (r > 1). Our algorithm uses the same input as the MSC algorithm and can find the same solution for rank-one tensor data as MSC., Comment: 13 pages, improved version, typos removed, text restructured, same results

We propose a new method of multiway clustering for 3-order tensors via affinity matrix (MCAM). Based on a notion of similarity between the tensor slices and the spread of information of each slice, our model builds an affinity/similarity matrix on which we apply advanced clustering methods. The combination of all clusters of the three modes delivers the desired multiway clustering. Finally, MCAM achieves competitive results compared with other known algorithms on synthetics and real datasets.

Bi-partite ribbon graphs arise in organising the large $N$ expansion of correlators in random matrix models and in the enumeration of observables in random tensor models. There is an algebra $\mathcal{K}(n)$, with basis given by bi-partite ribbon graphs with $n$ edges, which is useful in the applications to matrix and tensor models. The algebra $\mathcal{K}(n)$ is closely related to symmetric group algebras and has a matrix-block decomposition related to Clebsch-Gordan multiplicities, also known as Kronecker coefficients, for symmetric group representations. Quantum mechanical models which use $\mathcal{K}(n)$ as Hilbert spaces can be used to give combinatorial algorithms for computing the Kronecker coefficients., Comment: 13 pages, 1 figure. References updated, typos fixed. We thank the Editors Konstantinos Anagnostopoulos, Peter Schupp, George Zoupanos, for the invitation to contribute to this special volume on "Non-commutativity and physics". arXiv admin note: text overlap with arXiv:2010.04054