Maximal Rank of m × n × (mn - k) Tensors

It is shown that the maximal rank of m × n × ( m n - k ) tensors with k min {( m - 1 ) 2 /2 , ( n - 1 ) 2 /2} is greater than m n - 4Ö ### 2 k + O ( 1 ) . 1. INTRODUCTION A classical problem in algebraic computational complexity is to determine the minimal number of non-scalar multiplications required to evaluate some set S i ,j a i ,j ,k x i y j , k = 1, . . . , p , of bilinear forms in noncommuting variables x 1 , . . . , x m and y 1 , . . . , y n over a field F . This number is equal to the rank of the defining 3-tensor ( a i ,j ,k ) ÎF m ÄF n ÄF p , cf. [S]. An interesting problem, which does not depend on the coefficients a i ,j ,k , is the determination of R F ( m , n , p ) = max T ÎF m ÄF n ÄF p rank of T , the maximal rank of tensors in F m ÄF n ÄF p . This problem has been studied quite extensively in [AL1AS, Gat-J]. Atkinson and Stephens [AS] gave the following general reduction of R F ( m , n , m n - k ) with k min { m , n } to R F ( k , k , k 2 ..