Search

We prove that for every positive integer $d \ge 2$ there exist polynomial functions $F_d, G_d: \mathbb{N} \to \mathbb{N}$ such that for each positive integer $r$, every order-$d$ tensor $T$ over an arbitrary field and with partition rank at least $G_d(r)$ contains a $F_d(r) \times \cdots \times F_d(r)$ subtensor with partition rank at least $r$. We then deduce analogous results on the Schmidt rank of polynomials in zero or high characteristic., Comment: 10 pages

There are many notions of rank in multilinear algebra: tensor rank, partition rank, slice rank, and strength (or Schmidt rank) are a few examples. Typically the rank $\le r$ locus is not Zariski closed, and understanding the closure is an important problem. Our main theorem implies that for many notions of rank, the limits required to realize points in the closure do not become more complicated as the dimensions of the vector spaces increase. We phrase our results in the language of $\mathbf{GL}$-varieties, which are infinite dimensional algebraic varieties on which the infinite general linear group acts. In this guise, our main theorem states that for a map of $\mathbf{GL}$-varieties, points in the image closure can be realized as limits of 1-parameter families, just as in classical algebraic geometry., Comment: 22 pages

The 3-dimensional (3D) structure of the genome is of significant importance for many cellular processes. In this paper, we study the problem of reconstructing the 3D structure of chromosomes from Hi-C data of diploid organisms, which poses additional challenges compared to the better-studied haploid setting. With the help of techniques from algebraic geometry, we prove that a small amount of phased data is sufficient to ensure finite identifiability, both for noiseless and noisy data. In the light of these results, we propose a new 3D reconstruction method based on semidefinite programming, paired with numerical algebraic geometry and local optimization. The performance of this method is tested on several simulated datasets under different noise levels and with different amounts of phased data. We also apply it to a real dataset from mouse X chromosomes, and we are then able to recover previously known structural features., Comment: 19 + 3 pages, 5 + 3 figures

In connection with recent work on gaps in the asymptotic subranks of complex tensors the question arose whether the number of nonnegative real numbers that arise as the asymptotic subrank of some complex tensor is countable. In this short note we settle this question in the affirmative, for all tensor invariants that are algebraic in the sense that they are invariant under field automorphisms of the complex numbers.

Let $X$ be an affine scheme of $k \times \mathbb{N}$-matrices and $Y$ be an affine scheme of $\mathbb{N} \times \cdots \times \mathbb{N}$-dimensional tensors. The group Sym$(\mathbb{N})$ acts naturally on both $X$ and $Y$ and on their coordinate rings. We show that the Zariski closure of the image of a Sym$(\mathbb{N})$-equivariant morphism of schemes from $X$ to $Y$ is defined by finitely many Sym$(\mathbb{N})$-orbits in the coordinate ring of $Y$. Moreover, we prove that the closure of the image of this map is Sym$(\mathbb{N})$-Noetherian, that is, every descending chain of Sym$(\mathbb{N})$-stable closed subsets stabilizes.

A function $f: \mathbb{Z} \to \mathbb{Q}^n$ is a $c$-quasihomomorphism if the Hamming distance between $f(x+y)$ and $f(x)+f(y)$ is at most $c$ for all $x,y \in \mathbb{Z}$. We show that any $c$-quasihomomorphism has distance at most some constant $C(c)$ to an actual group homomorphism; here $C(c)$ depends only on $c$ and not on $n$ or $f$. This gives a positive answer to a special case of a question posed by Kazhdan and Ziegler., Comment: 9 pages, 1 figure, comments welcome

We define a GL-variety to be a (typically infinite dimensional) algebraic variety equipped with an action of the infinite general linear group under which the coordinate ring forms a polynomial representation. Such varieties have been used to study asymptotic properties of invariants like strength and tensor rank, and played a key role in two recent proofs of Stillman's conjecture. We initiate a systematic study of GL-varieties, and establish a number of foundational results about them. For example, we prove a version of Chevalley's theorem on constructible sets in this setting., 46 pages

This thesis was scanned from the print manuscript for digital preservation and is copyright the author. Researchers can access this thesis by asking their local university, institution or public library to make a request on their behalf. Monash staff and postgraduate students can use the link in the References field.

In this paper we extend earlier work on groups acting on Gaussian graphical models to Gaussian Bayesian networks and more general Gaussian models defined by chain graphs. We discuss the maximal group which leaves a given model invariant and provide basic statistical applications of this result. This includes equivariant estimation, maximal invariants and robustness. The computation of the group requires finding the essential graph. However, by applying Studeny's theory of imsets we show that computations for DAGs can be performed efficiently without building the essential graph. In our proof we derive simple necessary and sufficient conditions on vanishing sub-minors of the concentration matrix in the model.

Every Grassmannian, in its Pl��cker embedding, is defined by quadratic polynomials. We prove a vast, qualitative, generalisation of this fact to what we call Pl��cker varieties. A Pl��cker variety is in fact a family of varieties in exterior powers of vector spaces that, like the Grassmannian, is functorial in the vector space and behaves well under duals. A special case of our result says that for each fixed natural number k, the k-th secant variety of any Pl��cker-embedded Grassmannian is defined in bounded degree independent of the Grassmannian. Our approach is to take the limit of a Pl��cker variety in the dual of a highly symmetric space known as the infinite wedge, and to prove that up to symmetry the limit is defined by finitely many polynomial equations. For this we prove the auxilliary result that for every natural number p the space of p-tuples of infinite-by-infinite matrices is Noetherian modulo row and column operations. Our results have algorithmic counterparts: every bounded Pl��cker variety has a polynomial-time membership test, and the same holds for Zariski-closed, basis-independent properties of p-tuples of matrices., 25 pages, 4 figures

These lecture notes for the 2013 CIME/CIRM summer school Combinatorial Algebraic Geometry deal with manifestly infinite-dimensional algebraic varieties with large symmetry groups. So large, in fact, that subvarieties stable under those symmetry groups are defined by finitely many orbits of equations---whence the title Noetherianity up to symmetry. It is not the purpose of these notes to give a systematic, exhaustive treatment of such varieties, but rather to discuss a few "personal favourites": exciting examples drawn from applications in algebraic statistics and multilinear algebra. My hope is that these notes will attract other mathematicians to this vibrant area at the crossroads of combinatorics, commutative algebra, algebraic geometry, statistics, and other applications., Comment: To appear in Springer's LNM C.I.M.E. series; several typos fixed

Rota's basis conjecture states that in any square array of vectors whose rows are bases of a fixed vector space the vectors can be rearranged within their rows in such a way that afterwards not only the rows are bases, but also the columns. We discuss an online version of this conjecture, in which the permutation used for rearranging the vectors in a given row must be determined without knowledge of the vectors further down the array. The paper contains surprises both for those who believe this online basis conjecture at first glance, and for those who disbelieve it., Comment: several further edits, added another reference, final version, to appear in J Alg Comb

We introduce tropically unirational varieties, which are subvarieties of tori that admit dominant rational maps whose tropicalisation is surjective. The central (and unresolved) question is whether all unirational varieties are tropically unirational. We present several techniques for proving tropical unirationality, along with various examples., Comment: Submitted to Proceedings of the CIEM Workshop on Tropical Geometry

We consider a natural generalization of an abelian Hidden Subgroup Problem where the subgroups and their cosets correspond to graphs of linear functions over a finite field F with d elements. The hidden functions of the generalized problem are not restricted to be linear but can also be m-variate polynomial functions of total degree n>=2. The problem of identifying hidden m-variate polynomials of degree less or equal to n for fixed n and m is hard on a classical computer since Omega(sqrt{d}) black-box queries are required to guarantee a constant success probability. In contrast, we present a quantum algorithm that correctly identifies such hidden polynomials for all but a finite number of values of d with constant probability and that has a running time that is only polylogarithmic in d.

For any finite graph Gamma and any field K of characteristic unequal to 2 we construct an algebraic variety X over K whose K-points parameterise K-Lie algebras generated by extremal elements, corresponding to the vertices of the graph, with prescribed commutation relations, corresponding to the non-edges. After that, we study the case where Gamma is a connected, simply laced Dynkin diagram of finite or affine type. We prove that X is then an affine space, and that all points in an open dense subset of X parameterise Lie algebras isomorphic to a single fixed Lie algebra. If Gamma is of affine type, then this fixed Lie algebra is the split finite-dimensional simple Lie algebra corresponding to the associated finite-type Dynkin diagram. This gives a new construction of these Lie algebras, in which they come together with interesting degenerations, corresponding to points outside the open dense subset. Our results may prove useful for recognising these Lie algebras., Comment: We made many corrections suggested by a referee, and extended our results to positive characteristic greater than 2