-
Losing dimensions: Geometric memorization in generative diffusion
Authors:
Beatrice Achilli,
Enrico Ventura,
Gianluigi Silvestri,
Bao Pham,
Gabriel Raya,
Dmitry Krotov,
Carlo Lucibello,
Luca Ambrogioni
Abstract:
Generative diffusion processes are state-of-the-art machine learning models deeply connected with fundamental concepts in statistical physics. Depending on the dataset size and the capacity of the network, their behavior is known to transition from an associative memory regime to a generalization phase in a phenomenon that has been described as a glassy phase transition. Here, using statistical ph…
▽ More
Generative diffusion processes are state-of-the-art machine learning models deeply connected with fundamental concepts in statistical physics. Depending on the dataset size and the capacity of the network, their behavior is known to transition from an associative memory regime to a generalization phase in a phenomenon that has been described as a glassy phase transition. Here, using statistical physics techniques, we extend the theory of memorization in generative diffusion to manifold-supported data. Our theoretical and experimental findings indicate that different tangent subspaces are lost due to memorization effects at different critical times and dataset sizes, which depend on the local variance of the data along their directions. Perhaps counterintuitively, we find that, under some conditions, subspaces of higher variance are lost first due to memorization effects. This leads to a selective loss of dimensionality where some prominent features of the data are memorized without a full collapse on any individual training point. We validate our theory with a comprehensive set of experiments on networks trained both in image datasets and on linear manifolds, which result in a remarkable qualitative agreement with the theoretical predictions.
△ Less
Submitted 11 October, 2024;
originally announced October 2024.
-
Manifolds, Random Matrices and Spectral Gaps: The geometric phases of generative diffusion
Authors:
Enrico Ventura,
Beatrice Achilli,
Gianluigi Silvestri,
Carlo Lucibello,
Luca Ambrogioni
Abstract:
In this paper, we investigate the latent geometry of generative diffusion models under the manifold hypothesis. To this purpose, we analyze the spectrum of eigenvalues (and singular values) of the Jacobian of the score function, whose discontinuities (gaps) reveal the presence and dimensionality of distinct sub-manifolds. Using a statistical physics approach, we derive the spectral distributions a…
▽ More
In this paper, we investigate the latent geometry of generative diffusion models under the manifold hypothesis. To this purpose, we analyze the spectrum of eigenvalues (and singular values) of the Jacobian of the score function, whose discontinuities (gaps) reveal the presence and dimensionality of distinct sub-manifolds. Using a statistical physics approach, we derive the spectral distributions and formulas for the spectral gaps under several distributional assumptions and we compare these theoretical predictions with the spectra estimated from trained networks. Our analysis reveals the existence of three distinct qualitative phases during the generative process: a trivial phase; a manifold coverage phase where the diffusion process fits the distribution internal to the manifold; a consolidation phase where the score becomes orthogonal to the manifold and all particles are projected on the support of the data. This `division of labor' between different timescales provides an elegant explanation on why generative diffusion models are not affected by the manifold overfitting phenomenon that plagues likelihood-based models, since the internal distribution and the manifold geometry are produced at different time points during generation.
△ Less
Submitted 16 October, 2024; v1 submitted 8 October, 2024;
originally announced October 2024.
-
Learning and Unlearning: Bridging classification, memory and generative modeling in Recurrent Neural Networks
Authors:
Enrico Ventura
Abstract:
The human brain is a complex system that is fascinating scientists since a long time. Its remarkable capabilities include categorization of concepts, retrieval of memories and creative generation of new examples. At the same time, modern artificial neural networks are trained on large amounts of data to accomplish these same tasks with a considerable degree of precision. By contrast with biologica…
▽ More
The human brain is a complex system that is fascinating scientists since a long time. Its remarkable capabilities include categorization of concepts, retrieval of memories and creative generation of new examples. At the same time, modern artificial neural networks are trained on large amounts of data to accomplish these same tasks with a considerable degree of precision. By contrast with biological systems, machines appear to be either significantly slow and energetically expensive to train, suggesting the need for a paradigmatic change in the way they learn. We here review a general learning prescription that allows to perform classification, memorization and generation of new examples in bio-inspired artificial neural networks. The training procedure can be split into a prior Hebbian learning phase and a subsequent anti-Hebbian one (usually referred to as Unlearning). The separation of training in two epochs allows the algorithm to go fully unsupervised while partially aligning with some modern biological theories of learning.
△ Less
Submitted 8 October, 2024;
originally announced October 2024.
-
Quotient-saturated groups
Authors:
Jordi Delgado,
Mallika Roy,
Enric Ventura
Abstract:
We introduce the new notion of quotient-saturation as a measure of the immensity of the quotient structure of a group. We present a sufficient condition for a finitely presented group to be quotient-saturated, and use it to deduce that non-elementary finitely presented subgroups of a hyperbolic group (in particular, non-elementary hyperbolic groups themselves) are quotient-saturated. Finally, we e…
▽ More
We introduce the new notion of quotient-saturation as a measure of the immensity of the quotient structure of a group. We present a sufficient condition for a finitely presented group to be quotient-saturated, and use it to deduce that non-elementary finitely presented subgroups of a hyperbolic group (in particular, non-elementary hyperbolic groups themselves) are quotient-saturated. Finally, we elaborate on the previous results to extend the scope of this property to finitely presented acylindrically hyperbolic groups.
△ Less
Submitted 3 April, 2024;
originally announced April 2024.
-
Stallings automata
Authors:
Jordi Delgado,
Enric Ventura
Abstract:
This text aims to provide a self-contained, comprehensive, and reasonably detailed presentation of the theory of Stallings automata and some of its main applications.
This text aims to provide a self-contained, comprehensive, and reasonably detailed presentation of the theory of Stallings automata and some of its main applications.
△ Less
Submitted 13 September, 2024; v1 submitted 15 March, 2024;
originally announced March 2024.
-
Demolition and Reinforcement of Memories in Spin-Glass-like Neural Networks
Authors:
Enrico Ventura
Abstract:
Statistical mechanics has made significant contributions to the study of biological neural systems by modeling them as recurrent networks of interconnected units with adjustable interactions. Several algorithms have been proposed to optimize the neural connections to enable network tasks such as information storage (i.e. associative memory) and learning probability distributions from data (i.e. ge…
▽ More
Statistical mechanics has made significant contributions to the study of biological neural systems by modeling them as recurrent networks of interconnected units with adjustable interactions. Several algorithms have been proposed to optimize the neural connections to enable network tasks such as information storage (i.e. associative memory) and learning probability distributions from data (i.e. generative modeling). Among these methods, the Unlearning algorithm, aligned with emerging theories of synaptic plasticity, was introduced by John Hopfield and collaborators. The primary objective of this thesis is to understand the effectiveness of Unlearning in both associative memory models and generative models. Initially, we demonstrate that the Unlearning algorithm can be simplified to a linear perceptron model which learns from noisy examples featuring specific internal correlations. The selection of structured training data enables an associative memory model to retrieve concepts as attractors of a neural dynamics with considerable basins of attraction. Subsequently, a novel regularization technique for Boltzmann Machines is presented, proving to outperform previously developed methods in learning hidden probability distributions from data-sets. The Unlearning rule is derived from this new regularized algorithm and is showed to be comparable, in terms of inferential performance, to traditional Boltzmann-Machine learning.
△ Less
Submitted 4 March, 2024;
originally announced March 2024.
-
On the codimension of permanental varieties
Authors:
Ada Boralevi,
Enrico Carlini,
Mateusz Michałek,
Emanuele Ventura
Abstract:
In this article, we study permanental varieties, i.e. varieties defined by the vanishing of permanents of fixed size of a generic matrix. Permanents and their varieties play an important, and sometimes poorly understood, role in combinatorics. However, there are essentially no geometric results about them in the literature, in very sharp contrast to the well-behaved and ubiquitous case of determin…
▽ More
In this article, we study permanental varieties, i.e. varieties defined by the vanishing of permanents of fixed size of a generic matrix. Permanents and their varieties play an important, and sometimes poorly understood, role in combinatorics. However, there are essentially no geometric results about them in the literature, in very sharp contrast to the well-behaved and ubiquitous case of determinants and minors. Motivated by the study of the singular locus of the permanental hypersurface, we focus on the codimension of these varieties. We introduce a $\mathbb C^{*}$-action on matrices and prove a number of results. In particular, we improve a lower bound on the codimension of the aforementioned singular locus established by von zur Gathen in 1987.
△ Less
Submitted 27 February, 2024;
originally announced February 2024.
-
Semi-analytic modelling of Pop. III star formation and metallicity evolution -- I. Impact on the UV luminosity functions at z = 9-16
Authors:
Emanuele M. Ventura,
Yuxiang Qin,
Sreedhar Balu,
J. Stuart B. Wyithe
Abstract:
We implemented Population III (Pop. III) star formation in mini-halos within the MERAXES semi-analytic galaxy formation and reionisation model, run on top of a N-body simulation with $L = 10 h^{-1}$ cMpc with 2048$^3$ particles resolving all dark matter halos down to the mini-halos ($\sim 10^5 M_\odot$). Our modelling includes the chemical evolution of the IGM, with metals released through superno…
▽ More
We implemented Population III (Pop. III) star formation in mini-halos within the MERAXES semi-analytic galaxy formation and reionisation model, run on top of a N-body simulation with $L = 10 h^{-1}$ cMpc with 2048$^3$ particles resolving all dark matter halos down to the mini-halos ($\sim 10^5 M_\odot$). Our modelling includes the chemical evolution of the IGM, with metals released through supernova-driven bubbles that expand according to the Sedov-Taylor model. We found that SN-driven metal bubbles are generally small, with radii typically of 150 ckpc at z = 6. Hence, the majority of the first galaxies are likely enriched by their own star formation. However, as reionization progresses, the feedback effects from the UV background become more pronounced, leading to a halt in star formation in low-mass galaxies, after which external chemical enrichment becomes more relevant. We explore the sensitivity of the star formation rate density and stellar mass functions on the unknown values of free parameters. We also discuss the observability of Pop. III dominated systems with JWST, finding that the inclusion of Pop. III galaxies can have a significant effect on the total UV luminosity function at z = 12 - 16. Our results support the idea that the excess of bright galaxies detected with JWST might be explained by the presence of bright top-heavy Pop. III dominated galaxies without requiring an increased star formation efficiency.
△ Less
Submitted 21 February, 2024; v1 submitted 14 January, 2024;
originally announced January 2024.
-
Unlearning regularization for Boltzmann Machines
Authors:
Enrico Ventura,
Simona Cocco,
Rémi Monasson,
Francesco Zamponi
Abstract:
Boltzmann Machines (BMs) are graphical models with interconnected binary units, employed for the unsupervised modeling of data distributions. When trained on real data, BMs show the tendency to behave like critical systems, displaying a high susceptibility of the model under a small rescaling of the inferred parameters. This behaviour is not convenient for the purpose of generating data, because i…
▽ More
Boltzmann Machines (BMs) are graphical models with interconnected binary units, employed for the unsupervised modeling of data distributions. When trained on real data, BMs show the tendency to behave like critical systems, displaying a high susceptibility of the model under a small rescaling of the inferred parameters. This behaviour is not convenient for the purpose of generating data, because it slows down the sampling process, and induces the model to overfit the training-data. In this study, we introduce a regularization method for BMs to improve the robustness of the model under rescaling of the parameters. The new technique shares formal similarities with the unlearning algorithm, an iterative procedure used to improve memory associativity in Hopfield-like neural networks. We test our unlearning regularization on synthetic data generated by two simple models, the Curie-Weiss ferromagnetic model and the Sherrington-Kirkpatrick spin glass model. We show that it outperforms $L_p$-norm schemes and discuss the role of parameter initialization. Eventually, the method is applied to learn the activity of real neuronal cells, confirming its efficacy at shifting the inferred model away from criticality and coming out as a powerful candidate for actual scientific implementations.
△ Less
Submitted 15 May, 2024; v1 submitted 15 November, 2023;
originally announced November 2023.
-
Border apolarity and varieties of sums of powers
Authors:
Tomasz Mańdziuk,
Emanuele Ventura
Abstract:
We study border varieties of sums of powers ($\underline{\mathrm{VSP}}$'s for short), recently introduced by Buczyńska and Buczyński, parameterizing border rank decompositions of a point (e.g. of a tensor or a homogeneous polynomial) with respect to a smooth projective toric variety and living in the Haiman-Sturmfels multigraded Hilbert scheme. Their importance stems from the role of border tensor…
▽ More
We study border varieties of sums of powers ($\underline{\mathrm{VSP}}$'s for short), recently introduced by Buczyńska and Buczyński, parameterizing border rank decompositions of a point (e.g. of a tensor or a homogeneous polynomial) with respect to a smooth projective toric variety and living in the Haiman-Sturmfels multigraded Hilbert scheme. Their importance stems from the role of border tensor rank in theoretical computer science, especially in the estimation of the exponent of matrix multiplication, a fundamental and still unknown quantity in the theory of computation. We compare $\underline{\mathrm{VSP}}$'s to other well-known loci in the Hilbert scheme, parameterizing scheme-theoretic versions of decompositions. The latter ones are crucial in that they naturally explain the existing severe barriers to giving good lower bounds on ranks. We introduce the notion of border identifiability and provide sufficient criteria for its appearance, which rely on the multigraded regularity of Maclagan and Smith. We link border identifiability to wildness of points. Finally, we determine $\underline{\mathrm{VSP}}$'s in several instances and regimes, in the contexts of tensors and homogeneous polynomials. These include concise $3$-tensors of minimal border rank and in particular of border rank three.
△ Less
Submitted 14 February, 2024; v1 submitted 30 October, 2023;
originally announced October 2023.
-
Computation of endo-fixed closures in free-abelian times free groups
Authors:
Mallika Roy,
Enric Ventura
Abstract:
In this paper, we explore the behaviour of the fixed subgroups of endomorphisms of free-abelian times free (FATF) groups. We exhibit an algorithm which, given a finitely generated subgroup $\mathcal{H}$ of a FATF group $\mathcal{G}$, decides whether $\mathcal{H}$ is the fixed subgroup of some (finite) family of endomorphisms of $\mathcal{G}$ and, in the affirmative case, it finds such a family. Th…
▽ More
In this paper, we explore the behaviour of the fixed subgroups of endomorphisms of free-abelian times free (FATF) groups. We exhibit an algorithm which, given a finitely generated subgroup $\mathcal{H}$ of a FATF group $\mathcal{G}$, decides whether $\mathcal{H}$ is the fixed subgroup of some (finite) family of endomorphisms of $\mathcal{G}$ and, in the affirmative case, it finds such a family. The algorithm combines both combinatorial and algebraic methods.
△ Less
Submitted 26 July, 2023;
originally announced July 2023.
-
Memory Storage and Retrieval in Sparsely Connected Balanced Networks
Authors:
Enrico Ventura
Abstract:
Ever since the last two decades of the past century pioneering studies in the field of statistical physics had focused their efforts on developing models of neural networks that could display memory storage and retrieval. Though many associative memory models were easy to handle and still quite effective to explain the basic memory retrieval processes in the brain, they were not satisfactory under…
▽ More
Ever since the last two decades of the past century pioneering studies in the field of statistical physics had focused their efforts on developing models of neural networks that could display memory storage and retrieval. Though many associative memory models were easy to handle and still quite effective to explain the basic memory retrieval processes in the brain, they were not satisfactory under the biological point of view. It became clear to scientists that a biologically realistic neural network should have respected typical features that were observed in experiments of neurophysiology. This aspect has led to the introduction of Balanced Networks, systems where excitatory and inhibitory neurons balance their effect on each other as an emergent property of the network dynamics. One of such models is the exhibition of a mean level of neuronal activity (i.e. the average spiking rate of neurons) that is univocally defined by a linear equation in the external input. This aspect might help to reproduce what is measured in particular areas devoted to memory storage, i.e. a persistent activity during the memory retrieval performance. Even though progresses in the matter of balanced networks where achieved in the last two decades, there is still no complete theory that conciliates memory retrieval and balance in a network of neurons. The aim of this work is to develop a biologically plausible model that presents both balance and memory retrieval, building on a framework of mean field equations that can predict the theoretical behaviour of the network under the choice of a set of control parameters. We will thus measure the critical capacity of the system as a function of these parameters, comparing the theoretical results with the numerical simulations.
△ Less
Submitted 7 April, 2023;
originally announced May 2023.
-
The central tree property and algorithmic problems on subgroups of free groups
Authors:
Mallika Roy,
Enric Ventura,
Pascal Weil
Abstract:
We study the average case complexity of the uniform membership problem for subgroups of free groups, and we show that it is orders of magnitude smaller than the worst case complexity of the best known algorithms. This applies to subgroups given by a fixed number of generators as well as to subgroups given by an exponential number of generators. The main idea behind this result is to exploit a gene…
▽ More
We study the average case complexity of the uniform membership problem for subgroups of free groups, and we show that it is orders of magnitude smaller than the worst case complexity of the best known algorithms. This applies to subgroups given by a fixed number of generators as well as to subgroups given by an exponential number of generators. The main idea behind this result is to exploit a generic property of tuples of words, called the central tree property. An application is given to the average case complexity of the relative primitivity problem, using Shpilrain's recent algorithm to decide primitivity, whose average case complexity is a constant depending only on the rank of the ambient free group.
△ Less
Submitted 19 October, 2023; v1 submitted 26 March, 2023;
originally announced March 2023.
-
A note on very ample Terracini loci
Authors:
Edoardo Ballico,
Emanuele Ventura
Abstract:
In this short note we show that, for any ample embedding of a variety of dimension at least two in a projective space, all high enough degree Veronese re-embeddings have non-empty Terracini loci.
In this short note we show that, for any ample embedding of a variety of dimension at least two in a projective space, all high enough degree Veronese re-embeddings have non-empty Terracini loci.
△ Less
Submitted 22 March, 2023;
originally announced March 2023.
-
Training neural networks with structured noise improves classification and generalization
Authors:
Marco Benedetti,
Enrico Ventura
Abstract:
The beneficial role of noise-injection in learning is a consolidated concept in the field of artificial neural networks, suggesting that even biological systems might take advantage of similar mechanisms to optimize their performance. The training-with-noise algorithm proposed by Gardner and collaborators is an emblematic example of a noise-injection procedure in recurrent networks, which can be u…
▽ More
The beneficial role of noise-injection in learning is a consolidated concept in the field of artificial neural networks, suggesting that even biological systems might take advantage of similar mechanisms to optimize their performance. The training-with-noise algorithm proposed by Gardner and collaborators is an emblematic example of a noise-injection procedure in recurrent networks, which can be used to model biological neural systems. We show how adding structure to noisy training data can substantially improve the algorithm performance, allowing the network to approach perfect retrieval of the memories and wide basins of attraction, even in the scenario of maximal injected noise. We also prove that the so-called Hebbian Unlearning rule coincides with the training-with-noise algorithm when noise is maximal and data are stable fixed points of the network dynamics.
△ Less
Submitted 31 May, 2024; v1 submitted 26 February, 2023;
originally announced February 2023.
-
On the Koiran-Skomra's question about Hessians
Authors:
Edoardo Ballico,
Emanuele Ventura
Abstract:
We give a negative answer to a question of Koiran and Skomra about Hessians, motivated by Kayal's algorithm for the equivalence problem to the Fermat polynomial. We conjecture that our counterexamples are the only ones. We also study a local version of their question.
We give a negative answer to a question of Koiran and Skomra about Hessians, motivated by Kayal's algorithm for the equivalence problem to the Fermat polynomial. We conjecture that our counterexamples are the only ones. We also study a local version of their question.
△ Less
Submitted 20 January, 2023;
originally announced January 2023.
-
The role of Pop III stars and early black holes in the 21cm signal from Cosmic Dawn
Authors:
Emanuele M. Ventura,
Alessandro Trinca,
Raffaella Schneider,
Luca Graziani,
Rosa Valiante,
J. Stuart B. Wyithe
Abstract:
Modeling the 21cm global signal from the Cosmic Dawn is challenging due to the many poorly constrained physical processes that come into play. We address this problem using the semi-analytical code "Cosmic Archaeology Tool" (CAT). CAT follows the evolution of dark matter halos tracking their merger history and provides an ab initio description of their baryonic evolution, starting from the formati…
▽ More
Modeling the 21cm global signal from the Cosmic Dawn is challenging due to the many poorly constrained physical processes that come into play. We address this problem using the semi-analytical code "Cosmic Archaeology Tool" (CAT). CAT follows the evolution of dark matter halos tracking their merger history and provides an ab initio description of their baryonic evolution, starting from the formation of the first (Pop III) stars and black holes (BHs) in mini-halos at z > 20. The model is anchored to observations of galaxies and AGN at z < 6 and predicts a reionization history consistent with constraints. In this work we compute the evolution of the mean global 21cm signal between $4\leq z \leq 40$ based on the rate of formation and emission properties of stars and accreting black holes. We obtain an absorption profile with a maximum depth $δ{\rm T_b} = -95$ mK at $z \sim 26.5$ (54 MHz). This feature is quickly suppressed turning into an emission signal at $z = 20$ due to the contribution of accreting BHs that efficiently heat the IGM at $z < 27$. The high-$z$ absorption feature is caused by the early coupling between the spin and kinetic temperature of the IGM induced by Pop III star formation episodes in mini-halos. Once we account for an additional radio background from early BHs, we are able to reproduce the timing and the depth of the EDGES signal only if we consider a smaller X-ray background from accreting BHs, but not the shape.
△ Less
Submitted 18 January, 2023; v1 submitted 18 October, 2022;
originally announced October 2022.
-
SOXS mechanical integration and verification in Italy
Authors:
M. Aliverti,
F. Battaini,
K. Radhakrishnan,
M. Genoni,
G. Pariani,
L. Oggioni,
O. Hershko,
M. Colapietro,
S. D'Orsi,
A . Brucalassi,
G. Pignata,
H. Kuncarayakti,
S . Campana,
R. Claudi,
P. Schipani,
J . Achrén,
J. A. Araiza Duranm,
I. Arcavi,
A. Baruffolo,
S. Ben Ami,
R . Bruch,
G. Capasso,
E. Cappellaro,
R. Cosentino,
F. D'Alessio
, et al. (24 additional authors not shown)
Abstract:
SOXS (SOn of X-Shooter) is a medium resolution (~4500) wide-band (0.35 - 2.0 μm) spectrograph which passed the Final Design Review in 2018. The instrument is in the final integration phase and it is planned to be installed at the NTT in La Silla by next year. It is mainly composed of five different optomechanical subsystems (Common Path, NIR spectrograph, UV-VIS spectrograph, Camera, and Calibrati…
▽ More
SOXS (SOn of X-Shooter) is a medium resolution (~4500) wide-band (0.35 - 2.0 μm) spectrograph which passed the Final Design Review in 2018. The instrument is in the final integration phase and it is planned to be installed at the NTT in La Silla by next year. It is mainly composed of five different optomechanical subsystems (Common Path, NIR spectrograph, UV-VIS spectrograph, Camera, and Calibration) and other mechanical subsystems (Interface flange, Platform, cable corotator, and cooling system). A brief overview of the optomechanical subsystems is presented here as more details can be found in the specific proceedings while a more comprehensive discussion is dedicated to the other mechanical subsystems and the tools needed for the integration of the instrument. Moreover, the results obtained during the acceptance of the various mechanical elements are presented together with the experiments performed to validate the functionality of the subsystems. Finally, the mechanical integration procedure is shown here, along with all the modifications applied to correct the typical problems happening in this phase.
△ Less
Submitted 15 September, 2022;
originally announced September 2022.
-
Implicitisation and Parameterisation in Polynomial Functors
Authors:
Andreas Blatter,
Jan Draisma,
Emanuele Ventura
Abstract:
In earlier work, the second author showed that a closed subset of a polynomial functor can always be defined by finitely many polynomial equations. In follow-up work on $\operatorname{GL}\nolimits_{\infty}$-varieties, Bik-Draisma-Eggermont-Snowden showed, among other things, that in characteristic zero every such closed subset is the image of a morphism whose domain is the product of a finite-dime…
▽ More
In earlier work, the second author showed that a closed subset of a polynomial functor can always be defined by finitely many polynomial equations. In follow-up work on $\operatorname{GL}\nolimits_{\infty}$-varieties, Bik-Draisma-Eggermont-Snowden showed, among other things, that in characteristic zero every such closed subset is the image of a morphism whose domain is the product of a finite-dimensional affine variety and a polynomial functor. In this paper, we show that both results can be made algorithmic: there exists an algorithm $\mathbf{implicitise}$ that takes as input a morphism into a polynomial functor and outputs finitely many equations defining the closure of the image; and an algorithm $\mathbf{parameterise}$ that takes as input a finite set of equations defining a closed subset of a polynomial functor and outputs a morphism whose image is that closed subset.
△ Less
Submitted 3 June, 2022;
originally announced June 2022.
-
Quasihomomorphisms from the integers into Hamming metrics
Authors:
Jan Draisma,
Rob H. Eggermont,
Tim Seynnaeve,
Nafie Tairi,
Emanuele Ventura
Abstract:
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 questi…
▽ More
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.
△ Less
Submitted 18 April, 2022;
originally announced April 2022.
-
Autòmats de Stallings, un camí d'anada i tornada
Authors:
Jordi Delgado,
Enric Ventura
Abstract:
In this paper we review some of the fundamental properties of the free group and give a detailed account of Stallings's theory of automata, a geometric interpretation of its subgroups that has been (and still is) immensely fruitful, both as a means of understanding classical results, as as a source of new results. We review some of the most important ones. -- -
En aquest article revisem algunes de…
▽ More
In this paper we review some of the fundamental properties of the free group and give a detailed account of Stallings's theory of automata, a geometric interpretation of its subgroups that has been (and still is) immensely fruitful, both as a means of understanding classical results, as as a source of new results. We review some of the most important ones. -- -
En aquest article revisem algunes de les propietats fonamentals del group lliure i fem una exposició detallada de la teoria dels autòmats de Stallings, una interpretació geomètrica dels seus subgrups que ha estat (i segueix essent) immensament fructífera, tant com a mitjà per entendre resultats clàssics, com com a font de nous resultats. N'expliquem alguns dels més rellevants.
△ Less
Submitted 12 January, 2023; v1 submitted 15 February, 2022;
originally announced February 2022.
-
Supervised perceptron learning vs unsupervised Hebbian unlearning: Approaching optimal memory retrieval in Hopfield-like networks
Authors:
Marco Benedetti,
Enrico Ventura,
Enzo Marinari,
Giancarlo Ruocco,
Francesco Zamponi
Abstract:
The Hebbian unlearning algorithm, i.e. an unsupervised local procedure used to improve the retrieval properties in Hopfield-like neural networks, is numerically compared to a supervised algorithm to train a linear symmetric perceptron. We analyze the stability of the stored memories: basins of attraction obtained by the Hebbian unlearning technique are found to be comparable in size to those obtai…
▽ More
The Hebbian unlearning algorithm, i.e. an unsupervised local procedure used to improve the retrieval properties in Hopfield-like neural networks, is numerically compared to a supervised algorithm to train a linear symmetric perceptron. We analyze the stability of the stored memories: basins of attraction obtained by the Hebbian unlearning technique are found to be comparable in size to those obtained in the symmetric perceptron, while the two algorithms are found to converge in the same region of Gardner's space of interactions, having followed similar learning paths. A geometric interpretation of Hebbian unlearning is proposed to explain its optimal performances. Because the Hopfield model is also a prototypical model of disordered magnetic system, it might be possible to translate our results to other models of interest for memory storage in materials.
△ Less
Submitted 7 March, 2022; v1 submitted 31 December, 2021;
originally announced January 2022.
-
Degrees of Kalman varieties of tensors
Authors:
Zahra Shahidi,
Luca Sodomaco,
Emanuele Ventura
Abstract:
Kalman varieties of tensors are algebraic varieties consisting of tensors whose singular vector $k$-tuples lay on prescribed subvarieties. They were first studied by Ottaviani and Sturmfels in the context of matrices. We extend recent results of Ottaviani and the first author to the partially symmetric setting. We describe a generating function whose coefficients are the degrees of these varieties…
▽ More
Kalman varieties of tensors are algebraic varieties consisting of tensors whose singular vector $k$-tuples lay on prescribed subvarieties. They were first studied by Ottaviani and Sturmfels in the context of matrices. We extend recent results of Ottaviani and the first author to the partially symmetric setting. We describe a generating function whose coefficients are the degrees of these varieties and we analyze its asymptotics, providing analytic results à la Zeilberger and Pantone. We emphasize the special role of isotropic vectors in the spectral theory of tensors and describe the totally isotropic Kalman variety as a dual variety.
△ Less
Submitted 23 April, 2022; v1 submitted 20 September, 2021;
originally announced September 2021.
-
A list of applications of Stallings automata
Authors:
Jordi Delgado,
Enric Ventura
Abstract:
This survey is intended to be a fast (and reasonably updated) reference for the theory of Stallings automata and its applications to the study of subgroups of the free group, with the main accent on algorithmic aspects. Consequently, results concerning finitely generated subgroups have greater prominence in the paper. However, when possible, we try to state the results with more generality, includ…
▽ More
This survey is intended to be a fast (and reasonably updated) reference for the theory of Stallings automata and its applications to the study of subgroups of the free group, with the main accent on algorithmic aspects. Consequently, results concerning finitely generated subgroups have greater prominence in the paper. However, when possible, we try to state the results with more generality, including the usually overlooked non-(finitely-generated) case.
△ Less
Submitted 11 June, 2022; v1 submitted 2 September, 2021;
originally announced September 2021.
-
Intersection configurations in free and free times free-abelian groups
Authors:
Jordi Delgado,
Mallika Roy,
Enric Ventura
Abstract:
In this paper we study intersection configurations -- which describe the behaviour of multiple (finite) intersections of subgroups with respect to finite generability -- in the realm of free and free times free-abelian (FTFA) groups. We say that a configuration is realizable in a group $G$ if there exist subgroups $H_1,\ldots , H_k \leqslant G$ realizing it.
It is well known that free groups…
▽ More
In this paper we study intersection configurations -- which describe the behaviour of multiple (finite) intersections of subgroups with respect to finite generability -- in the realm of free and free times free-abelian (FTFA) groups. We say that a configuration is realizable in a group $G$ if there exist subgroups $H_1,\ldots , H_k \leqslant G$ realizing it.
It is well known that free groups $\mathbb{F}_n$ satisfy the Howson property: the intersection of any two finitely generated subgroups is again finitely generated. We show that the Howson property is indeed the only obstruction for multiple intersection configurations to be realizable within nonabelian free groups.
On the contrary, FTFA groups $\mathbb{F}_n \times \mathbb{Z}^m$ are well known to be non-Howson. We also study multiple intersections within FTFA groups, providing an algorithm to decide, given $k\geq 2$ finitely generated subgroups, whether their intersection is again finitely generated and, in the affirmative case, compute a `basis' for it. We finally prove that any intersection configuration is realizable in a FTFA group $\mathbb{F}_n \times \mathbb{Z}^m$, for $n\geq 2$ and big enough $m$. As a consequence, we exhibit finitely presented groups where every intersection configuration is realizable.
△ Less
Submitted 29 July, 2023; v1 submitted 26 July, 2021;
originally announced July 2021.
-
Relative order and spectrum in free and related groups
Authors:
Jordi Delgado,
Enric Ventura,
Alexander Zakharov
Abstract:
In this paper, we consider a natural generalization of the concept of order of an element in a group: an element $g \in G$ is said to have order $k$ in a subgroup $H$ of $G$ (\resp \wrt a coset $Hu$) if $k$ is the first strictly positive integer such that $g^k \in H$ (\resp $g^k \in Hu$). We study this notion and its algorithmic properties in the realm of free groups and some related families.
B…
▽ More
In this paper, we consider a natural generalization of the concept of order of an element in a group: an element $g \in G$ is said to have order $k$ in a subgroup $H$ of $G$ (\resp \wrt a coset $Hu$) if $k$ is the first strictly positive integer such that $g^k \in H$ (\resp $g^k \in Hu$). We study this notion and its algorithmic properties in the realm of free groups and some related families.
Both positive and negative (algorithmic) results emerge in this setting. On the positive side, among other results, we prove that the order of elements, the set of orders (called spectrum), and the set of preorders (\ie the set of elements of a given order) \wrt finitely generated subgroups are always computable in free and free times free-abelian groups. On the negative side, we provide examples of groups and subgroups having essentially any subset of natural numbers as relative spectrum; in particular, non-recursive and even non-recursively enumerable sets of natural numbers. Also, we take advantage of Mikhailova's construction to see that the spectrum membership problem is unsolvable for direct products of nonabelian free groups.
△ Less
Submitted 8 May, 2021;
originally announced May 2021.
-
Modeling differential rates of aging using routine laboratory data; Implications for morbidity and health care expenditure
Authors:
Alix Jean Santos,
Xavier Eugenio Asuncion,
Camille Rivero-Co,
Maria Eloisa Ventura,
Reynaldo Geronia II,
Lauren Bangerter,
Natalie E. Sheils
Abstract:
Aging is a multidimensional process where phenotypes change at varying rates. Longitudinal studies of aging typically involve following a cohort of individuals over the course of several years. This design is hindered by cost, attrition, and subsequently small sample size. Alternative methodologies are therefore warranted. In this study, we used a variational autoencoder to estimate rates of aging…
▽ More
Aging is a multidimensional process where phenotypes change at varying rates. Longitudinal studies of aging typically involve following a cohort of individuals over the course of several years. This design is hindered by cost, attrition, and subsequently small sample size. Alternative methodologies are therefore warranted. In this study, we used a variational autoencoder to estimate rates of aging from cross-sectional data from routine laboratory tests of 1.4 million individuals collected from 2016 to 2019. By incorporating metrics that would ensure model's stability and distinctness of the dimensions, we uncovered four aging dimensions that represent the following bodily functions: 1) kidney, 2) thyroid, 3) white blood cells, and 4) liver and heart. We then examined the relationship between rates of aging on morbidity and health care expenditure. In general, faster agers along these dimensions are more likely to develop chronic diseases that are related to these bodily functions. They also had higher health care expenditures compared to the slower agers. K-means clustering of individuals based on rate of aging revealed that clusters with higher odds of developing morbidity had the highest cost across all types of health care services. Results suggest that cross-sectional laboratory data can be leveraged as an alternative methodology to understand age along the different dimensions. Moreover, rates of aging are differentially related to future costs, which can aid in the development of interventions to delay disease progression.
△ Less
Submitted 17 March, 2021;
originally announced March 2021.
-
Strength and slice rank of forms are generically equal
Authors:
Edoardo Ballico,
Arthur Bik,
Alessandro Oneto,
Emanuele Ventura
Abstract:
We prove that strength and slice rank of homogeneous polynomials of degree $d \geq 5$ over an algebraically closed field of characteristic zero coincide generically. To show this, we establish a conjecture of Catalisano, Geramita, Gimigliano, Harbourne, Migliore, Nagel and Shin concerning dimensions of secant varieties of the varieties of reducible homogeneous polynomials. These statements were al…
▽ More
We prove that strength and slice rank of homogeneous polynomials of degree $d \geq 5$ over an algebraically closed field of characteristic zero coincide generically. To show this, we establish a conjecture of Catalisano, Geramita, Gimigliano, Harbourne, Migliore, Nagel and Shin concerning dimensions of secant varieties of the varieties of reducible homogeneous polynomials. These statements were already known in degrees $2\leq d\leq 7$ and $d=9$.
△ Less
Submitted 23 February, 2021;
originally announced February 2021.
-
Onto extensions of free groups
Authors:
Sebastià Mijares,
Enric Ventura
Abstract:
An extension of subgroups $H\leqslant K\leqslant F_A$ of the free group of rank $|A|=r\geqslant 2$ is called onto when, for every ambient free basis $A'$, the Stallings graph $Γ_{A'}(K)$ is a quotient of $Γ_{A'}(H)$. Algebraic extensions are onto and the converse implication was conjectured by Miasnikov-Ventura-Weil, and resolved in the negative, first by Parzanchevski-Puder for rank $r=2$, and re…
▽ More
An extension of subgroups $H\leqslant K\leqslant F_A$ of the free group of rank $|A|=r\geqslant 2$ is called onto when, for every ambient free basis $A'$, the Stallings graph $Γ_{A'}(K)$ is a quotient of $Γ_{A'}(H)$. Algebraic extensions are onto and the converse implication was conjectured by Miasnikov-Ventura-Weil, and resolved in the negative, first by Parzanchevski-Puder for rank $r=2$, and recently by Kolodner for general rank. In this note we study properties of this new type of extension among free groups (as well as the fully onto variant), and investigate their corresponding closure operators. Interestingly, the natural attempt for a dual notion -- into extensions -- becomes trivial, making a Takahasi type theorem not possible in this setting.
△ Less
Submitted 10 April, 2021; v1 submitted 29 December, 2020;
originally announced December 2020.
-
The development status of the NIR Arm of the new SoXS instrument at the ESO/NTT telescope
Authors:
F. Vitali,
M. Aliverti,
G. Capasso,
F. D'Alessio,
M. Munari,
M. Riva,
S. Scuderi,
R. Zanmar Sanchez,
S. Campana,
P. Schipani,
R. Claudi,
A. Baruffolo,
S. Ben-Ami,
F. Biondi,
A. Brucalassi,
R. Cosentino,
D. Ricci,
P. D'Avanzo,
H. Kuncarayakti,
A. Rubin,
J. Achrén,
J. A. Araiza-Duran,
I. Arcavi,
A. Bianco,
R. Bruch
, et al. (23 additional authors not shown)
Abstract:
We present here the development status of the NIR spectrograph of the Son Of X-Shooter (SOXS) instrument, for the ESO/NTT telescope at La Silla (Chile). SOXS is a R~4,500 mean resolution spectrograph, with a simultaneously coverage from about 0.35 to 2.00 micron. It will be mounted at the Nasmyth focus of the NTT. The two UV-VIS-NIR wavelength ranges will be covered by two separated arms. The NIR…
▽ More
We present here the development status of the NIR spectrograph of the Son Of X-Shooter (SOXS) instrument, for the ESO/NTT telescope at La Silla (Chile). SOXS is a R~4,500 mean resolution spectrograph, with a simultaneously coverage from about 0.35 to 2.00 micron. It will be mounted at the Nasmyth focus of the NTT. The two UV-VIS-NIR wavelength ranges will be covered by two separated arms. The NIR spectrograph is a fully cryogenic echelle-dispersed spectrograph, working in the range 0.80-2.00 micron, equipped with a Hawaii H2RG IR array from Teledyne. The whole spectrograph will be cooled down to about 150 K (but the array at 40 K), to lower the thermal background, and equipped with a thermal filter to block any thermal radiation above 2.0 micron. In this work, we will show the advanced phase of integration of the NIR spectrograph.
△ Less
Submitted 23 December, 2020;
originally announced December 2020.
-
Manufacturing, integration, and mechanical verification of SOXS
Authors:
M. Aliverti,
L. Oggioni,
M. Genoni,
G. Pariani,
O. Hershko,
A. Brucalassi,
G. Pignata,
H. Kuncarayakti,
R. Zanmar Sanchez,
M. Munari,
S. Campana,
P. Schipani,
R. Claudi,
A. Baruffolo,
S. Ben-Ami,
F. Biondi,
G. Capasso,
R. Cosentino,
F. D'Alessio,
P. D'Avanzo,
M. Landoni,
A. Rubin,
S. Scuderi,
F. Vitali,
D. Young
, et al. (24 additional authors not shown)
Abstract:
SOXS (Son Of X-Shooter) is a medium resolution (~4500) wide-band (0.35 - 2.0 μm) spectrograph which passed the Final Design Review in 2018. The instrument is planned to be installed at the NTT in La Silla and it is mainly composed by five different optomechanical subsystems (Common Path, NIR spectrograph, UV-VIS spectrograph, Camera, and Calibration) and other mechanical subsystems (Interface flan…
▽ More
SOXS (Son Of X-Shooter) is a medium resolution (~4500) wide-band (0.35 - 2.0 μm) spectrograph which passed the Final Design Review in 2018. The instrument is planned to be installed at the NTT in La Silla and it is mainly composed by five different optomechanical subsystems (Common Path, NIR spectrograph, UV-VIS spectrograph, Camera, and Calibration) and other mechanical subsystems (Interface flange, Platform, cable corotator, and cooling). It is currently in the procurement and integration phase. In this paper we present the post-FDR modifications in the mechanical design due to the various iterations with the manufacturers and the actual procurement status. The last part describes the strategy used to keep under control the mechanical interfaces between the subsystems.
△ Less
Submitted 23 December, 2020;
originally announced December 2020.
-
The set of forms with bounded strength is not closed
Authors:
Edoardo Ballico,
Arthur Bik,
Alessandro Oneto,
Emanuele Ventura
Abstract:
The strength of a homogeneous polynomial (or form) is the smallest length of an additive decomposition expressing it whose summands are reducible forms. Using polynomial functors, we show that the set of forms with bounded strength is not always Zariski-closed. More specifically, if the ground field is algebraically closed, we prove that the set of quartics with strength $\leq3$ is not Zariski-clo…
▽ More
The strength of a homogeneous polynomial (or form) is the smallest length of an additive decomposition expressing it whose summands are reducible forms. Using polynomial functors, we show that the set of forms with bounded strength is not always Zariski-closed. More specifically, if the ground field is algebraically closed, we prove that the set of quartics with strength $\leq3$ is not Zariski-closed for a large number of variables.
△ Less
Submitted 2 November, 2021; v1 submitted 2 December, 2020;
originally announced December 2020.
-
Asymptotics of degrees and ED degrees of Segre products
Authors:
Giorgio Ottaviani,
Luca Sodomaco,
Emuanuele Ventura
Abstract:
Two fundamental invariants attached to a projective variety are its classical algebraic degree and its Euclidean Distance degree (ED degree). In this paper, we study the asymptotic behavior of these two degrees of some Segre products and their dual varieties. We analyze the asymptotics of degrees of (hypercubical) hyperdeterminants, the dual hypersurfaces to Segre varieties. We offer an alternativ…
▽ More
Two fundamental invariants attached to a projective variety are its classical algebraic degree and its Euclidean Distance degree (ED degree). In this paper, we study the asymptotic behavior of these two degrees of some Segre products and their dual varieties. We analyze the asymptotics of degrees of (hypercubical) hyperdeterminants, the dual hypersurfaces to Segre varieties. We offer an alternative viewpoint on the stabilization of the ED degree of some Segre varieties. Although this phenomenon was incidentally known from Friedland-Ottaviani's formula expressing the number of singular vector tuples of a general tensor, our approach provides a geometric explanation. Finally, we establish the stabilization of the degree of the dual variety of a Segre product $X\times Q_{n}$, where $X$ is a projective variety and $Q_n\subset \mathbb{P}^{n+1}$ is a smooth quadric hypersurface.
△ Less
Submitted 17 June, 2021; v1 submitted 26 August, 2020;
originally announced August 2020.
-
The strength for line bundles
Authors:
Edoardo Ballico,
Emanuele Ventura
Abstract:
We introduce the strength for sections of a line bundle on an algebraic variety. This generalizes the strength of homogeneous polynomials that has been recently introduced to resolve Stillman's conjecture, an important problem in commutative algebra. We establish the first properties of this notion and give some tool to obtain upper bounds on the strength in this framework. Moreover, we show some…
▽ More
We introduce the strength for sections of a line bundle on an algebraic variety. This generalizes the strength of homogeneous polynomials that has been recently introduced to resolve Stillman's conjecture, an important problem in commutative algebra. We establish the first properties of this notion and give some tool to obtain upper bounds on the strength in this framework. Moreover, we show some results on the usual strength such as the reducibility of the set of strength two homogeneous polynomials.
△ Less
Submitted 3 April, 2020;
originally announced April 2020.
-
Vanishing Hessian, wild forms and their border VSP
Authors:
Hang Huang,
Mateusz Michałek,
Emanuele Ventura
Abstract:
Wild forms are homogeneous polynomials whose smoothable rank is strictly larger than their border rank. The discrepancy between these two ranks is caused by the difference between the limit of spans of a family of zero-dimensional schemes and the span of their flat limit. For concise forms of minimal border rank, we show that the condition of vanishing Hessian is equivalent to being wild. This is…
▽ More
Wild forms are homogeneous polynomials whose smoothable rank is strictly larger than their border rank. The discrepancy between these two ranks is caused by the difference between the limit of spans of a family of zero-dimensional schemes and the span of their flat limit. For concise forms of minimal border rank, we show that the condition of vanishing Hessian is equivalent to being wild. This is proven by making a detour through structure tensors of smoothable and Gorenstein algebras. The equivalence fails in the non-minimal border rank regime. We exhibit an infinite series of minimal border rank wild forms of every degree $d\geq 3$ as well as an infinite series of wild cubics. Inspired by recent work on border apolarity of Buczyńska and Buczyński, we study the border varieties of sums of powers $\underline{\mathrm{VSP}}$ of these forms in the corresponding multigraded Hilbert schemes.
△ Less
Submitted 25 June, 2020; v1 submitted 31 December, 2019;
originally announced December 2019.
-
Entry loci and ranks
Authors:
Edoardo Ballico,
Emanuele Ventura
Abstract:
We study entry loci of varieties and their irreducibility from the perspective of $X$-ranks with respect to a projective variety $X$. These loci are the closures of the points that appear in an $X$-rank decomposition of a general point in the ambient space. We look at entry loci of low degree normal surfaces in $\mathbb P^4$ using Segre points of curves; the smooth case was classically studied by…
▽ More
We study entry loci of varieties and their irreducibility from the perspective of $X$-ranks with respect to a projective variety $X$. These loci are the closures of the points that appear in an $X$-rank decomposition of a general point in the ambient space. We look at entry loci of low degree normal surfaces in $\mathbb P^4$ using Segre points of curves; the smooth case was classically studied by Franchetta. We introduce a class of varieties whose generic rank coincides with the one of its general entry locus, and show that any smooth and irreducible projective variety admits an embedding with this property.
△ Less
Submitted 1 December, 2019;
originally announced December 2019.
-
Multiple populations in globular clusters and their parent galaxies
Authors:
A. P. Milone,
A. F. Marino,
G. S. Da Costa,
E. P. Lagioia,
F. D'Antona,
P. Goudfrooij,
H. Jerjen,
D. Massari,
A. Renzini,
D. Yong,
H. Baumgardt,
G. Cordoni,
E. Dondoglio,
C. Li,
M. Tailo,
R. Asa'd,
E. M. Ventura
Abstract:
The 'chromosome map' diagram (ChM) proved a successful tool to identify and characterize multiple populations (MPs) in 59 Galactic Globular Clusters (GCs). Here, we construct ChMs for 11 GCs of both Magellanic Clouds (MCs) and with different ages to compare MPs in Galactic and extra-Galactic environments, and explore whether this phenomenon is universal through 'place' and 'time'. MPs are detected…
▽ More
The 'chromosome map' diagram (ChM) proved a successful tool to identify and characterize multiple populations (MPs) in 59 Galactic Globular Clusters (GCs). Here, we construct ChMs for 11 GCs of both Magellanic Clouds (MCs) and with different ages to compare MPs in Galactic and extra-Galactic environments, and explore whether this phenomenon is universal through 'place' and 'time'. MPs are detected in five clusters. The fractions of 1G stars, ranging from about 50% to more than 80%, are significantly higher than those observed in Galactic GCs with similar present-day masses. By considering both Galactic and MC clusters, the fraction of 1G stars exhibits: (i) a strong anti-correlation with the present-day mass, and (ii) with the present-day mass of 2G stars; (iii) a mild anti-correlation with 1G present-day mass. All Galactic clusters without MPs have initial masses smaller than ~1.5 10^5 solar masses but a mass threshold governing the occurrence of MPs seems challenged by massive simple-population MC GCs; (iv) Milky Way clusters with large perigalactic distances typically host larger fractions of 1G stars, but the difference disappears when we use initial cluster masses. These facts are consistent with a scenario where the stars lost by GCs mostly belong to the 1G. By exploiting recent work based on Gaia, half of the known Type II GCs appear clustered in a distinct region of the integral of motions space, thus suggesting a common progenitor galaxy. Except for these Type II GCs,we do not find any significant difference in the MPs between clusters associated with different progenitors.
△ Less
Submitted 21 October, 2019;
originally announced October 2019.
-
Stallings automata for free-times-abelian groups: intersections and index
Authors:
Jordi Delgado,
Enric Ventura
Abstract:
We extend the classical Stallings theory (describing subgroups of free groups as automata) to direct products of free and abelian groups: after introducing enriched automata (i.e., automata with extra abelian labels), we obtain an explicit bijection between subgroups and a certain type of such enriched automata, which - as it happens in the free group - is computable in the finitely generated case…
▽ More
We extend the classical Stallings theory (describing subgroups of free groups as automata) to direct products of free and abelian groups: after introducing enriched automata (i.e., automata with extra abelian labels), we obtain an explicit bijection between subgroups and a certain type of such enriched automata, which - as it happens in the free group - is computable in the finitely generated case.
This approach provides a neat geometric description of (even non finitely generated) intersections of finitely generated subgroups within this non-Howson family. In particular, we give a geometric solution to the subgroup intersection problem and the finite index problem, providing recursive bases and transversals respectively.
△ Less
Submitted 10 June, 2022; v1 submitted 13 October, 2019;
originally announced October 2019.
-
Labels of real projective varieties
Authors:
Edoardo Ballico,
Emanuele Ventura
Abstract:
Let $X$ be a complex projective variety defined over $\mathbb R$. Recently, Bernardi and the first author introduced the notion of admissible rank with respect to $X$. This rank takes into account only decompositions that are stable under complex conjugation. Such a decomposition carries a label, i.e., a pair of integers recording the cardinality of its totally real part. We study basic properties…
▽ More
Let $X$ be a complex projective variety defined over $\mathbb R$. Recently, Bernardi and the first author introduced the notion of admissible rank with respect to $X$. This rank takes into account only decompositions that are stable under complex conjugation. Such a decomposition carries a label, i.e., a pair of integers recording the cardinality of its totally real part. We study basic properties of admissible ranks for varieties, along with special examples of curves; for instance, for rational normal curves admissible and complex ranks coincide. Along the way, we introduce the scheme theoretic version of admissible rank. Finally, analogously to the situation of real ranks, we analyze typical labels, i.e., those arising as labels of a full-dimensional Euclidean open set. We highlight similarities and differences with typical ranks.
△ Less
Submitted 24 September, 2019;
originally announced September 2019.
-
Tensors with maximal symmetries
Authors:
Austin Conner,
Fulvio Gesmundo,
Joseph M. Landsberg,
Emanuele Ventura
Abstract:
We classify tensors with maximal and next to maximal dimensional symmetry groups under a natural genericity assumption (1-genericity), in dimensions greater than 7. In other words, we classify minimal dimensional orbits in the space of (m,m,m) tensors assuming 1-genericity. Our study uncovers new tensors with striking geometry. This paper was motivated by Strassen's laser method for bounding the e…
▽ More
We classify tensors with maximal and next to maximal dimensional symmetry groups under a natural genericity assumption (1-genericity), in dimensions greater than 7. In other words, we classify minimal dimensional orbits in the space of (m,m,m) tensors assuming 1-genericity. Our study uncovers new tensors with striking geometry. This paper was motivated by Strassen's laser method for bounding the exponent of matrix multiplication. The best known tensor for the laser method is the large Coppersmith-Winograd tensor, and our study began with the observation that it has a large symmetry group, of dimension m^2/2 +m/2. We show that in odd dimensions, this is the largest possible for a 1-generic tensor, but in even dimensions we exhibit a tensor with a larger dimensional symmetry group. In the course of the proof, we classify nondegenerate bilinear forms with large dimensional stabilizers, which may be of interest in its own right.
△ Less
Submitted 8 October, 2021; v1 submitted 20 September, 2019;
originally announced September 2019.
-
Rank and border rank of Kronecker powers of tensors and Strassen's laser method
Authors:
Austin Conner,
Fulvio Gesmundo,
Joseph M. Landsberg,
Emanuele Ventura
Abstract:
We prove that the border rank of the Kronecker square of the little Coppersmith-Winograd tensor $T_{cw,q}$ is the square of its border rank for $q > 2$ and that the border rank of its Kronecker cube is the cube of its border rank for $q > 4$. This answers questions raised implicitly in [Coppersmith-Winograd, 1990] and explicitly in [Bläser, 2013] and rules out the possibility of proving new upper…
▽ More
We prove that the border rank of the Kronecker square of the little Coppersmith-Winograd tensor $T_{cw,q}$ is the square of its border rank for $q > 2$ and that the border rank of its Kronecker cube is the cube of its border rank for $q > 4$. This answers questions raised implicitly in [Coppersmith-Winograd, 1990] and explicitly in [Bläser, 2013] and rules out the possibility of proving new upper bounds on the exponent of matrix multiplication using the square or cube of a little Coppersmith-Winograd tensor in this range.
In the positive direction, we enlarge the list of explicit tensors potentially useful for Strassen's laser method, introducing a skew-symmetric version of the Coppersmith-Winograd tensor, $T_{skewcw,q}$. For $q = 2$, the Kronecker square of this tensor coincides with the $3\times 3$ determinant polynomial, $\det_3 \in \mathbb{C}^9\otimes \mathbb{C}^9\otimes \mathbb{C}^9$, regarded as a tensor. We show that this tensor could potentially be used to show that the exponent of matrix multiplication is two.
We determine new upper bounds for the (Waring) rank and the (Waring) border rank of $\det_3$, exhibiting a strict submultiplicative behaviour for $T_{skewcw,2}$ which is promising for the laser method.
We establish general results regarding border ranks of Kronecker powers of tensors, and make a detailed study of Kronecker squares of tensors in $\mathbb{C}^3\otimes \mathbb{C}^3\otimes \mathbb{C}^3$.
△ Less
Submitted 27 December, 2021; v1 submitted 10 September, 2019;
originally announced September 2019.
-
Geometric conditions for strict submultiplicativity of rank and border rank
Authors:
Edoardo Ballico,
Alessandra Bernardi,
Fulvio Gesmundo,
Alessandro Oneto,
Emanuele Ventura
Abstract:
The $X$-rank of a point $p$ in projective space is the minimal number of points of an algebraic variety $X$ whose linear span contains $p$. This notion is naturally submultiplicative under tensor product. We study geometric conditions that guarantee strict submultiplicativity. We prove that in the case of points of rank two, strict submultiplicativity is entirely characterized in terms of the tris…
▽ More
The $X$-rank of a point $p$ in projective space is the minimal number of points of an algebraic variety $X$ whose linear span contains $p$. This notion is naturally submultiplicative under tensor product. We study geometric conditions that guarantee strict submultiplicativity. We prove that in the case of points of rank two, strict submultiplicativity is entirely characterized in terms of the trisecant lines to the variety. Moreover, we focus on the case of curves: we prove that for curves embedded in an even-dimensional projective space, there are always points for which strict submultiplicativity occurs, with the only exception of rational normal curves.
△ Less
Submitted 27 May, 2020; v1 submitted 9 September, 2019;
originally announced September 2019.
-
Strict inclusions of high rank loci
Authors:
Edoardo Ballico,
Alessandra Bernardi,
Emanuele Ventura
Abstract:
For a given projective variety $X$, the high rank loci are the closures of the sets of points whose $X$-rank is higher than the generic one. We show examples of strict inclusion between two consecutive high rank loci. Our first example is for the Veronese surface of plane quartics. Although Piene had already shown an example when $X$ is a curve, we construct infinitely many curves in…
▽ More
For a given projective variety $X$, the high rank loci are the closures of the sets of points whose $X$-rank is higher than the generic one. We show examples of strict inclusion between two consecutive high rank loci. Our first example is for the Veronese surface of plane quartics. Although Piene had already shown an example when $X$ is a curve, we construct infinitely many curves in $\mathbb P^4$ for which such strict inclusion appears. For space curves, we give two criteria to check whether the locus of points of maximal rank 3 is finite (possibly empty).
△ Less
Submitted 14 July, 2019;
originally announced July 2019.
-
Minimal degree equations for curves and surfaces (variations on a theme of Halphen)
Authors:
Edoardo Ballico,
Emanuele Ventura
Abstract:
Many classical results in algebraic geometry arise from investigating some extremal behaviors that appear among projective varieties not lying on any hypersurface of fixed degree. We study two numerical invariants attached to such collections of varieties: their minimal degree and their maximal number of linearly independent smallest degree hypersurfaces passing through them. We show results for c…
▽ More
Many classical results in algebraic geometry arise from investigating some extremal behaviors that appear among projective varieties not lying on any hypersurface of fixed degree. We study two numerical invariants attached to such collections of varieties: their minimal degree and their maximal number of linearly independent smallest degree hypersurfaces passing through them. We show results for curves and surfaces, and pose several questions.
△ Less
Submitted 19 June, 2019;
originally announced June 2019.
-
Fixed subgroups and computation of auto-fixed closures in free-abelian times free groups
Authors:
Mallika Roy,
Enric Ventura
Abstract:
The classical result by Dyer--Scott about fixed subgroups of finite order automorphisms of $F_n$ being free factors of $F_n$ is no longer true in $Z^m\times F_n$. Within this more general context, we prove a relaxed version in the spirit of Bestvina--Handel Theorem: the rank of fixed subgroups of finite order automorphisms is uniformly bounded in terms of $m,n$. We also study periodic points of en…
▽ More
The classical result by Dyer--Scott about fixed subgroups of finite order automorphisms of $F_n$ being free factors of $F_n$ is no longer true in $Z^m\times F_n$. Within this more general context, we prove a relaxed version in the spirit of Bestvina--Handel Theorem: the rank of fixed subgroups of finite order automorphisms is uniformly bounded in terms of $m,n$. We also study periodic points of endomorphisms of $Z^m\times F_n$, and give an algorithm to compute auto-fixed closures of finitely generated subgroups of $Z^m\times F_n$. On the way, we prove the analog of Day's Theorem for real elements in $Z^m\times F_n$, contributing a modest step into the project of doing so for any right angled Artin group (as McCool did with respect to Whitehead's Theorem in the free context).
△ Less
Submitted 5 June, 2019;
originally announced June 2019.
-
Singular Curves of Low Degree and Multifiltrations from Osculating Spaces
Authors:
Jarosław Buczyński,
Nathan Ilten,
Emanuele Ventura
Abstract:
In order to study projections of smooth curves, we introduce multifiltrations obtained by combining flags of osculating spaces. We classify all configurations of singularities occurring for a projection of a smooth curve embedded by a complete linear system away from a projective linear space of dimension at most two. In particular, we determine all configurations of singularities of non-degenerat…
▽ More
In order to study projections of smooth curves, we introduce multifiltrations obtained by combining flags of osculating spaces. We classify all configurations of singularities occurring for a projection of a smooth curve embedded by a complete linear system away from a projective linear space of dimension at most two. In particular, we determine all configurations of singularities of non-degenerate degree d rational curves in $\mathbb{P}^n$ when $d - n \leq 3$ and $d < 2n$. Along the way, we describe the Schubert cycles giving rise to these projections.
We also reprove a special case of the Castelnuovo bound using these multifiltrations: under the assumption $d < 2n$, the arithmetic genus of any nondegenerate degree $d$ curve in $\mathbb{P}^n$ is at most $d - n$.
△ Less
Submitted 12 January, 2020; v1 submitted 28 May, 2019;
originally announced May 2019.
-
The monic rank
Authors:
Arthur Bik,
Jan Draisma,
Alessandro Oneto,
Emanuele Ventura
Abstract:
We introduce the monic rank of a vector relative to an affine-hyperplane section of an irreducible Zariski-closed affine cone $X$. We show that the monic rank is finite and greater than or equal to the usual $X$-rank. We describe an algorithmic technique based on classical invariant theory to determine, in concrete situations, the maximal monic rank. Using this technique, we establish three new in…
▽ More
We introduce the monic rank of a vector relative to an affine-hyperplane section of an irreducible Zariski-closed affine cone $X$. We show that the monic rank is finite and greater than or equal to the usual $X$-rank. We describe an algorithmic technique based on classical invariant theory to determine, in concrete situations, the maximal monic rank. Using this technique, we establish three new instances of a conjecture due to B. Shapiro which states that a binary form of degree $d\cdot e$ is the sum of $d$ $d$-th powers of forms of degree $e$. Furthermore, in the case where $X$ is the cone of highest weight vectors in an irreducible representation---this includes the well-known cases of tensor rank and symmetric rank---we raise the question whether the maximal rank equals the maximal monic rank. We answer this question affirmatively in several instances.
△ Less
Submitted 11 November, 2019; v1 submitted 31 January, 2019;
originally announced January 2019.
-
Degrees of compression and inertia for free-abelian times free groups
Authors:
Mallika Roy,
Enric Ventura
Abstract:
We introduce the concepts of degree of inertia, $\text{di}_G(H)$, and degree of compression, $\text{dc}_G(H)$, of a finitely generated subgroup $H$ of a given group $G$. For the case of direct products of free-abelian and free groups, we compute the degree of compression and give an upper bound for the degree of inertia. Imposing some technical assumptions to the supremum involved in the definitio…
▽ More
We introduce the concepts of degree of inertia, $\text{di}_G(H)$, and degree of compression, $\text{dc}_G(H)$, of a finitely generated subgroup $H$ of a given group $G$. For the case of direct products of free-abelian and free groups, we compute the degree of compression and give an upper bound for the degree of inertia. Imposing some technical assumptions to the supremum involved in the definition of degree of inertia, we introduce the notion called restricted degree of inertia, $\text{di}'_G(H)$, and, again for the case $\mathbb{Z}^m \times F_n$, we provide an explicit formula relating it to the restricted degree of inertia of its projection to the free part, $\text{di}'_{F_n}(Hπ)$.
△ Less
Submitted 28 February, 2020; v1 submitted 9 January, 2019;
originally announced January 2019.
-
Fixed subgroups in direct products of surface groups of Euclidean type
Authors:
Jianchun Wu,
Enric Ventura,
Qiang Zhang
Abstract:
We give an explicit characterization of which direct products $G$ of surface groups of Euclidean type satisfy that the fixed subgroup of any automorphism (or endomorphism) of $G$ is compressed, and of which is it always inert.
We give an explicit characterization of which direct products $G$ of surface groups of Euclidean type satisfy that the fixed subgroup of any automorphism (or endomorphism) of $G$ is compressed, and of which is it always inert.
△ Less
Submitted 7 December, 2018;
originally announced December 2018.
-
Injective linear series of algebraic curves on quadrics
Authors:
Edoardo Ballico,
Emanuele Ventura
Abstract:
We study linear series on curves inducing injective morphisms to projective space, using zero-dimensional schemes and cohomological vanishings. Albeit projections of curves and their singularities are of central importance in algebraic geometry, basic problems still remain unsolved. In this note, we study cuspidal projections of space curves lying on irreducible quadrics (in arbitrary characterist…
▽ More
We study linear series on curves inducing injective morphisms to projective space, using zero-dimensional schemes and cohomological vanishings. Albeit projections of curves and their singularities are of central importance in algebraic geometry, basic problems still remain unsolved. In this note, we study cuspidal projections of space curves lying on irreducible quadrics (in arbitrary characteristic).
△ Less
Submitted 4 May, 2020; v1 submitted 6 December, 2018;
originally announced December 2018.
