Ubiquity of synonymity: almost all large binary trees are not uniquely identified by their spectra or their immanantal polynomials

We show for any of these choices of matrix that the fraction of binary trees with a unique spectrum goes to zero as the number of leaves goes to infinity. We investigate the rate of convergence of the above fraction to zero using numerical methods. For the adjacency and Laplacian matrices, we show that the a priori more informative immanantal polynomials have no greater power to distinguish between trees.Our results show that a generic large binary tree is highly unlikely to be identified uniquely by common spectral invariants.Tree shape theory furnishes numerical statistics about the structure of a tree [1,2]. (Because we are interested in applications of tree statistics to trees that describe the structure of branching events in evolutionary histories, we will, for convenience, always take the term tree without any qualifiers to mean a rooted, binary tree without any branch length information or labeling of the vertices.) Such statistics have two related uses. Firstly, they can be used in an attempt to tell whether two trees are actually the same and, secondly, they can be used to indicate the degree of similarity between two trees with respect to some criterion.Examples of the latter use are the testing of hypotheses about macroevolutionary processes and the detection of bias in phylogenetic reconstruction. Historically, numerical statistics for such purposes have attempted to capture the notion of the balance of a tree, which is the degree to which daughter subtrees are the same size. The balance is typically measured by ad-hoc formulae that are often selected for statistical power to distinguish between two different distributions on trees [3,4]. In previous work we investigated the possibility of describing the shape of the tree using a list of numbers rather than just a single number [5,6].A mathematically "canonical" approach to finding a list of such numbers is to use information derived from matrix representations of the trees. We first describe the matrix