Search

We prove that in the algebraic metacomplexity framework, the decomposition of metapolynomials into their isotypic components can be implemented efficiently, namely with only a quasipolynomial blowup in the circuit size. This means that many existing algebraic complexity lower bound proofs can be efficiently converted into isotypic lower bound proofs via highest weight metapolynomials, a notion studied in geometric complexity theory. In the context of algebraic natural proofs, our result means that without loss of generality algebraic natural proofs can be assumed to be isotypic. Our proof is built on the Poincar\'e--Birkhoff--Witt theorem for Lie algebras and on Gelfand--Tsetlin theory, for which we give the necessary comprehensive background., Comment: 29 pages. Comments are welcome!

We study the problem of characterizing linear preserver subgroups of algebraic varieties, with a particular emphasis on secant varieties and other varieties of tensors. We introduce a number of techniques built on different geometric properties of the varieties of interest. Our main result is a simple characterization of the linear preservers of secant varieties of Segre varieties in many cases, including $\sigma_r((\mathbb{P}^{n-1})^{\times k})$ for all $r \leq n^{\lfloor k/2 \rfloor}$. We also characterize the linear preservers of several other sets of tensors, including subspace varieties, the variety of slice rank one tensors, symmetric tensors of bounded Waring rank, the variety of biseparable tensors, and hyperdeterminantal surfaces. Computational techniques and applications in quantum information theory are discussed. We provide geometric proofs for several previously known results on linear preservers., Comment: 25 pages. Comments are welcome

Border complexity measures are defined via limits (or topological closures), so that any function which can approximated arbitrarily closely by low complexity functions itself has low border complexity. Debordering is the task of proving an upper bound on some non-border complexity measure in terms of a border complexity measure, thus getting rid of limits. Debordering is at the heart of understanding the difference between Valiant's determinant vs permanent conjecture, and Mulmuley and Sohoni's variation which uses border determinantal complexity. The debordering of matrix multiplication tensors by Bini played a pivotal role in the development of efficient matrix multiplication algorithms. Consequently, debordering finds applications in both establishing computational complexity lower bounds and facilitating algorithm design. Currently, very few debordering results are known. In this work, we study the question of debordering the border Waring rank of polynomials. Waring and border Waring rank are very well studied measures in the context of invariant theory, algebraic geometry, and matrix multiplication algorithms. For the first time, we obtain a Waring rank upper bound that is exponential in the border Waring rank and only linear in the degree. All previous known results were exponential in the degree. For polynomials with constant border Waring rank, our results imply an upper bound on the Waring rank linear in degree, which previously was only known for polynomials with border Waring rank at most 5., Comment: 22 pages; accepted at STACS 2024; this is an edited part of the preprint arXiv:2211.07055

We describe the minimal free resolution of the ideal of $2 \times 2$ subpermanents of a $2 \times n$ generic matrix $M$. In contrast to the case of $2 \times 2$ determinants, the $2 \times 2$ permanents define an ideal which is neither prime nor Cohen-Macaulay. We combine work of Laubenbacher-Swanson on the Gr\"obner basis of an ideal of $2 \times 2$ permanents of a generic matrix with our previous work connecting the initial ideal of $2 \times 2$ permanents to a simplicial complex. The main technical tool is a spectral sequence arising from the Bernstein-Gelfand-Gelfand correspondence., Comment: v1: 24 pages, 4 figures, v2: changes made to reflect referee input

In this article, we introduce the $k$-th collineation variety of a third order tensor. This is the closure of the image of the rational map of size $k$ minors of a matrix of linear forms associated to the tensor. We classify such varieties in the case of pencils of matrices, and nets of matrices of small size. We discuss the natural stratification of tensor spaces induced by the invariants and the geometric type of the collineation varieties., Comment: 19 pages, one ancillary file. Comments are welcome

We study algebraic complexity classes and their complete polynomials under \emph{homogeneous linear} projections, not just under the usual affine linear projections that were originally introduced by Valiant in 1979. These reductions are weaker yet more natural from a geometric complexity theory (GCT) standpoint, because the corresponding orbit closure formulations do not require the padding of polynomials. We give the \emph{first} complete polynomials for VF, the class of sequences of polynomials that admit small algebraic formulas, under homogeneous linear projections: The sum of the entries of the non-commutative elementary symmetric polynomial in 3 by 3 matrices of homogeneous linear forms. Even simpler variants of the elementary symmetric polynomial are hard for the topological closure of a large subclass of VF: the sum of the entries of the non-commutative elementary symmetric polynomial in 2 by 2 matrices of homogeneous linear forms, and homogeneous variants of the continuant polynomial (Bringmann, Ikenmeyer, Zuiddam, JACM '18). This requires a careful study of circuits with arity-3 product gates., Comment: This is edited part of preprint arXiv:2211.07055

It is a classical result that there are $12$ (irreducible) rational cubic curves through $8$ generic points in $\mathbb{P}_{\mathbb{C}}^2$, but little is known about the non-generic cases. The space of $8$-point configurations is partitioned into strata depending on combinatorial objects we call quatroids, a higher-order version of representable matroids. We compute all $779777$ quatroids on eight distinct points in the plane, which produces a full description of the stratification. For each stratum, we generate several invariants, including the number of rational cubics through a generic configuration. As a byproduct of our investigation, we obtain a collection of results regarding the base loci of pencils of cubics and positive certificates for non-rationality., Comment: 34 pages, 11 figures, 5 tables. Comments are welcome!

We lay the geometric foundations for the study of the characteristic polynomial of tensors. For symmetric tensors of order $d \geq 3$ and dimension $2$ and symmetric tensors of order $3$ and dimension $3$, we prove that only finitely many tensors share any given characteristic polynomial, unlike the case of symmetric matrices and the case of non-symmetric tensors. We propose precise conjectures for the dimension of the variety of tensors sharing the same characteristic polynomial, in the symmetric and in the non-symmetric setting., Comment: 25 pages, comments are welcome

Recent works of Costa-Dalai, Christandl-Gesmundo-Zuiddam, Blatter-Draisma-Rupniewski, and Bri\"et-Christandl-Leigh-Shpilka-Zuiddam have investigated notions of discreteness and gaps in the possible values that asymptotic tensor ranks can take. In particular, it was shown that the asymptotic subrank and asymptotic slice rank of any nonzero 3-tensor is equal to 1, equal to 1.88, or at least 2 (over any field), and that the set of possible values of these parameters is discrete (in several regimes). We determine exactly the next gap, showing that the asymptotic subrank and asymptotic slice rank of any nonzero 3-tensor is equal to 1, equal to 1.88, equal to 2, or at least 2.68.

A chopped ideal is obtained from a homogeneous ideal by considering only the generators of a fixed degree. We investigate cases in which the chopped ideal defines the same finite set of points as the original one-dimensional ideal. The complexity of computing these points from the chopped ideal is governed by the Hilbert function and regularity. We conjecture values for these invariants and prove them in many cases. We show that our conjecture is of practical relevance for symmetric tensor decomposition., Comment: 30 pages, 2 figures, comments are welcome! v2: Fixed typos thanks to referee reports. Numbering in section 2 changed slightly. To appear in J.Algebra

This is a collection of open problems and research ideas following the presentations and the discussions of the AGATES Kickoff Workshop held at the Institute of Mathematics of the Polish Academy of Sciences (IMPAN) and at the Department of Mathematics of University of Warsaw (MIM UW), September 19-26, 2022., Comment: Comments are welcome. Final version also available at https://agates.mimuw.edu.pl/index.php/research-reports-and-notes

We study Waring rank decompositions for cubic forms of rank $n+2$ in $n+1$ variables. In this setting, we prove that if a concise form has more than one non-redundant decomposition of length $n+2$, then all such decompositions share at least $n-3$ elements, and the remaining elements lie in a special configuration. Following this result, we give a detailed description of the $(n+2)$-th Terracini locus of the third Veronese embedding of $n$-dimensional projective space., Comment: 15 pages. Final version

Tensors are often studied by introducing preorders such as restriction and degeneration: the former describes transformations of the tensors by local linear maps on its tensor factors; the latter describes transformations where the local linear maps may vary along a curve, and the resulting tensor is expressed as a limit along this curve. In this work we introduce and study partial degeneration, a special version of degeneration where one of the local linear maps is constant whereas the others vary along a curve. Motivated by algebraic complexity, quantum entanglement and tensor networks, we present constructions based on matrix multiplication tensors and find examples by making a connection to the theory of prehomogeneous tensor spaces. We highlight the subtleties of this new notion by showing obstruction and classification results for the unit tensor. To this end, we study the notion of aided rank, a natural generalization of tensor rank. The existence of partial degenerations gives strong upper bounds on the aided rank of a tensor, which allows one to turn degenerations into restrictions. In particular, we present several examples, based on the W-tensor and the Coppersmith-Winograd tensors, where lower bounds on aided rank provide obstructions to the existence of certain partial degenerations., Comment: 31 pages, final version

The quantum max-flow quantifies the maximal possible entanglement between two regions of a tensor network state for a fixed graph and fixed bond dimensions. In this work, we calculate the quantum max-flow exactly in the case of the bridge graph. The result is achieved by drawing connections to the theory of prehomogenous tensor and the representation theory of quivers. Further, we highlight relations to invariant theory and to algebraic statistics., Comment: 26 pages, comments welcome

The subrank of tensors is a measure of how much a tensor can be ''diagonalized''. This parameter was introduced by Strassen to study fast matrix multiplication algorithms in algebraic complexity theory and is closely related to many central tensor parameters (e.g. slice rank, partition rank, analytic rank, geometric rank, G-stable rank) and problems in combinatorics, computer science and quantum information theory. Strassen (J. Reine Angew. Math., 1988) proved that there is a gap in the subrank when taking large powers under the tensor product: either the subrank of all powers is at most one, or it grows as a power of a constant strictly larger than one. In this paper, we precisely determine this constant for tensors of any order. Additionally, for tensors of order three, we prove that there is a second gap in the possible rates of growth. Our results strengthen the recent work of Costa and Dalai (J. Comb. Theory, Ser. A, 2021), who proved a similar gap for the slice rank. Our theorem on the subrank has wider applications by implying such gaps not only for the slice rank, but for any ``normalized monotone''. In order to prove the main result, we characterize when a tensor has a very structured tensor (the W-tensor) in its orbit closure. Our methods include degenerations in Grassmanians, which may be of independent interest., Comment: 25 pages. Final version

De-bordering is the task of proving that a border complexity measure is bounded from below, by a non-border complexity measure. This task is at the heart of understanding the difference between Valiant's determinant vs permanent conjecture, and Mulmuley and Sohoni's Geometric Complexity Theory (GCT) approach to settle the P \neq NP conjecture. Currently, very few de-bordering results are known. In this work, we study the question of de-bordering the border Waring rank of polynomials. Waring and border Waring rank are very well studied measures, in the context of invariant theory, algebraic geometry and matrix multiplication algorithms. For the first time, we obtain a Waring rank upper bound that is exponential in the border Waring rank and only *linear* in the degree. All previous results were known to be exponential in the degree. According to Kumar's recent surprising result (ToCT'20), a small border Waring rank implies that the polynomial can be approximated as a sum of a constant and a small product of linear polynomials. We prove the converse of Kumar's result, and in this way we de-border Kumar's complexity, and obtain a new formulation of border Waring rank, up to a factor of the degree. We phrase this new formulation as the orbit closure problem of the product-plus-power polynomial, and we successfully de-border this orbit closure. We fully implement the GCT approach against the power sum, and we generalize the ideas of Ikenmeyer-Kandasamy (STOC'20) to this new orbit closure. In this way, we obtain new multiplicity obstructions that are constructed from just the symmetries of the points and representation theoretic branching rules, rather than explicit multilinear computations. Furthermore, we realize that the generalization of our converse of Kumar's theorem to square matrices gives a homogeneous formulation of Ben-Or and Cleve (SICOMP'92). This results ...

We analyze Kumar's recent quadratic algebraic branching program size lower bound proof method (CCC 2017) for the power sum polynomial. We present a refinement of this method that gives better bounds in some cases. The lower bound relies on Noether-Lefschetz type conditions on the hypersurface defined by the homogeneous polynomial. In the explicit example that we provide, the lower bound is proved resorting to classical intersection theory. Furthermore, we use similar methods to improve the known lower bound methods for slice rank of polynomials. We consider a sequence of polynomials that have been studied before by Shioda and show that for these polynomials the improved lower bound matches the known upper bound., Comment: 14 pages

We study a class of semialgebraic convex bodies called discotopes. These are instances of zonoids, objects of interest in real algebraic geometry and random geometry. We focus on the face structure and on the boundary hypersurface of discotopes, highlighting interesting birational properties which may be investigated using tools from algebraic geometry. When a discotope is the Minkowski sum of two-dimensional discs, the Zariski closure of its set of extreme points is an irreducible hypersurface. In this case, we provide an upper bound for the degree of the hypersurface, drawing connections to the theory of classical determinantal varieties., Comment: 22 pages, 4 figures. Journal version

We introduce the broad subclass of algebraic compressed sensing problems, where structured signals are modeled either explicitly or implicitly via polynomials. This includes, for instance, low-rank matrix and tensor recovery. We employ powerful techniques from algebraic geometry to study well-posedness of sufficiently general compressed sensing problems, including existence, local recoverability, global uniqueness, and local smoothness. Our main results are summarized in thirteen questions and answers in algebraic compressed sensing. Most of our answers concerning the minimum number of required measurements for existence, recoverability, and uniqueness of algebraic compressed sensing problems are optimal and depend only on the dimension of the model., Comment: 30 pages, 1 figure

The tensor network variety is a variety of tensors associated to a graph and a set of positive integer weights on its edges, called bond dimensions. We determine an upper bound on the dimension of the tensor network variety. A refined upper bound is given in cases relevant for applications such as varieties of matrix product states and projected entangled pairs states. We provide a range (the "supercritical range") of the parameters where the upper bound is sharp., Comment: 27 pages, 3 figures. Final version, to appear in Communications in Contemporary Mathematics

Whereas matrix rank is additive under direct sum, in 1981 Sch\"onhage showed that one of its generalizations to the tensor setting, tensor border rank, can be strictly subadditive for tensors of order three. Whether border rank is additive for higher order tensors has remained open. In this work, we settle this problem by providing analogs of Sch\"onhage's construction for tensors of order four and higher. Sch\"onhage's work was motivated by the study of the computational complexity of matrix multiplication; we discuss implications of our results for the asymptotic rank of higher order generalizations of the matrix multiplication tensor., Comment: 26 pages, 5 figures. Final version accepted in SIMAX

Tensor network states form a variational ansatz class widely used, both analytically and numerically, in the study of quantum many-body systems. It is known that if the underlying graph contains a cycle, e.g. as in projected entangled pair states (PEPS), then the set of tensor network states of given bond dimension is not closed. Its closure is the tensor network variety. Recent work has shown that states on the boundary of this variety can yield more efficient representations for states of physical interest, but it remained unclear how to systematically find and optimize over such representations. We address this issue by defining a new ansatz class of states that includes states at the boundary of the tensor network variety of given bond dimension. We show how to optimize over this class in order to find ground states of local Hamiltonians by only slightly modifying standard algorithms and code for tensor networks. We apply this new method to a different of models and observe favorable energies and runtimes when compared with standard tensor network methods., Comment: 20 pages, 6 figures. Close to published version

We compute the degree of Stiefel manifolds, that is, the variety of orthonormal frames in a finite dimensional vector space. Our approach employs techniques from classical algebraic geometry, algebraic combinatorics, and classical invariant theory., Comment: 24 pages, Final version accepted in ECA

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., Comment: Much cleaner proof of main theorem and additional results added

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\"aser, 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$., Comment: Final Version

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., Comment: 21 pages

We investigate an extension of a lower bound on the Waring (cactus) rank of homogeneous forms due to Ranestad and Schreyer. We show that for particular classes of homogeneous forms, for which a generalization of this method applies, the lower bound extends to the level of border (cactus) rank. The approach is based on recent results on tensor asymptotic rank., Comment: 12 pages; Comments are welcome

We make a first geometric study of three varieties in $\mathbb{C}^m \otimes \mathbb{C}^m \otimes \mathbb{C}^m$ (for each $m$), including the Zariski closure of the set of tight tensors, the tensors with continuous regular symmetry. Our motivation is to develop a geometric framework for Strassen's Asymptotic Rank Conjecture that the asymptotic rank of any tight tensor is minimal. In particular, we determine the dimension of the set of tight tensors. We prove that this dimension equals the dimension of the set of oblique tensors, a less restrictive class introduced by Strassen., Comment: Final version. Revisions in Section 1 and Section 3

A symmetric tensor may be regarded as a partially symmetric tensor in several different ways. These produce different notions of rank for the symmetric tensor which are related by chains of inequalities. By exploiting algebraic tools such as apolarity theory, we show how the study of the simultaneous symmetric rank of partial derivatives of the homogeneous polynomial associated to the symmetric tensor can be used to prove equalities among different partially symmetric ranks. This approach aims to understand to what extent the symmetries of a tensor affect its rank. We apply this to the special cases of binary forms, ternary and quaternary cubics, monomials, and elementary symmetric polynomials., Comment: 28 pp

Given tensors $T$ and $T'$ of order $k$ and $k'$ respectively, the tensor product $T \otimes T'$ is a tensor of order $k+k'$. It was recently shown that the tensor rank can be strictly submultiplicative under this operation ([Christandl-Jensen-Zuiddam]). We study this phenomenon for symmetric tensors where additional techniques from algebraic geometry become available. The tensor product of symmetric tensors results in a partially symmetric tensor and our results amount to bounds on the partially symmetric rank. Following motivations from algebraic complexity theory and quantum information theory, we focus on the so-called "W-states", namely monomials of the form $x^{d-1}y$, and on products of such. In particular, we prove that the partially symmetric rank of $x^{d_1 -1}y \otimes ... \otimes x^{d_k-1} y$ is at most $2^{k-1}(d_1+ ... +d_k)$., Comment: 24 pages, 2 figures, final version to appear in Atti Accad. Naz. Lincei Rend. Lincei Mat. Appl

In this note we discuss the geometry of matrix product states with periodic boundary conditions and provide three infinite sequences of examples where the quantum max-flow is strictly less than the quantum min-cut. In the first we fix the underlying graph to be a 4-cycle and verify a prediction of Hastings that inequality occurs for infinitely many bond dimensions. In the second we generalize this result to a 2d-cycle. In the third we show that the 2d-cycle with periodic boundary conditions gives inequality for all d when all bond dimensions equal two, namely a gap of at least 2^{d-2} between the quantum max-flow and the quantum min-cut., Comment: 12 pages, 3 figures - Final version accepted for publication on J. Math. Phys

It has recently been shown that the tensor rank can be strictly submultiplicative under the tensor product, where the tensor product of two tensors is a tensor whose order is the sum of the orders of the two factors. The necessary upper bounds were obtained with help of border rank. It was left open whether border rank itself can be strictly submultiplicative. We answer this question in the affirmative. In order to do so, we construct lines in projective space along which the border rank drops multiple times and use this result in conjunction with a previous construction for a tensor rank drop. Our results also imply strict submultiplicativity for cactus rank and border cactus rank., Comment: 25 pages, 1 figure - Revised version

We give an upper bound for the cactus rank of any multi-homogeneous polynomial., Comment: Few more references. Improvement on the growth of the bound

We answer a question of K. Mulmuley: In [Efremenko-Landsberg-Schenck-Weyman] it was shown that the method of shifted partial derivatives cannot be used to separate the padded permanent from the determinant. Mulmuley asked if this "no-go" result could be extended to a model without padding. We prove this is indeed the case using the iterated matrix multiplication polynomial. We also provide several examples of polynomials with maximal space of partial derivatives, including the complete symmetric polynomials. We apply Koszul flattenings to these polynomials to have the first explicit sequence of polynomials with symmetric border rank lower bounds higher than the bounds attainable via partial derivatives., Comment: 18 pages - final version to appear in Theory of Computing

Valiant's famous determinant versus permanent problem is the flagship problem in algebraic complexity theory. Mulmuley and Sohoni (Siam J Comput 2001, 2008) introduced geometric complexity theory, an approach to study this and related problems via algebraic geometry and representation theory. Their approach works by multiplying the permanent polynomial with a high power of a linear form (a process called padding) and then comparing the orbit closures of the determinant and the padded permanent. This padding was recently used heavily to show no-go results for the method of shifted partial derivatives (Efremenko, Landsberg, Schenck, Weyman, 2016) and for geometric complexity theory (Ikenmeyer Panova, FOCS 2016 and B\"urgisser, Ikenmeyer Panova, FOCS 2016). Following a classical homogenization result of Nisan (STOC 1991) we replace the determinant in geometric complexity theory with the trace of a variable matrix power. This gives an equivalent but much cleaner homogeneous formulation of geometric complexity theory in which the padding is removed. This radically changes the representation theoretic questions involved to prove complexity lower bounds. We prove that in this homogeneous formulation there are no orbit occurrence obstructions that prove even superlinear lower bounds on the complexity of the permanent. This is the first no-go result in geometric complexity theory that rules out superlinear lower bounds in some model. Interestingly---in contrast to the determinant---the trace of a variable matrix power is not uniquely determined by its stabilizer., Comment: 21 pages. Final version to appear: Differential Geometry and its Applications - Special issue in Geometry and Complexity Theory

This paper studies geometric properties of the Iterated Matrix Multiplication polynomial and the hypersurface that it defines. We focus on geometric aspects that may be relevant for complexity theory such as the symmetry group of the polynomial, the dual variety and the Jacobian loci of the hypersurface, that are computed with the aid of representation theory of quivers., Comment: 20 pages - minor typos have been fixed - final version to appear in Journal of Algebra

We use algebraic geometry to study matrix rigidity, and more generally, the complexity of computing a matrix-vector product, continuing a study initiated by Kumar, et. al. We (i) exhibit many non-obvious equations testing for (border) rigidity, (ii) compute degrees of varieties associated to rigidity, (iii) describe algebraic varieties associated to families of matrices that are expected to have super-linear rigidity, and (iv) prove results about the ideals and degrees of cones that are of interest in their own right., Comment: 29 pages, final version to appear in FOCM

This paper studies the defectivity of secant varieties of Segre varieties. We prove that there exists an asymptotic lower estimate for the greater non-defective secant variety (without filling the ambient space) of any given Segre variety. In particular, we prove that the ratio between the greater non-defective secant variety of a Segre variety and its expected rank is lower bounded by a value depending just on the number of factors of the Segre variety. Moreover, in the final section, we present some results obtained by explicit computation, proving the non-defectivity of all the secant varieties of Segre varieties of the shape (P^n)^4, with 1 < n < 11, except at most \sigma_199((P^8)^4) and \sigma_357((P^10)^4)., Comment: 14 pages