2018/09/28 by Janzer, Oliver · 1 citation
#11B30 #Combinatorics (math.CO) #FOS: Mathematics #Number Theory (math.NT)
paper · doi:10.48550/arxiv.1809.10931
A tensor defined over a finite field \mathbbF has low analytic rank if the distribution of its values differs significantly from the uniform distribution. An order d tensor has partition rank 1 if it can be written as a product of two tensors of order less than d, and it has partition rank at most k if it can be written as a sum of k tensors of partition rank 1. In this paper, we prove that if the analytic rank of an order d tensor is at most r, then its partition rank is at most f(r,d,|\mathbbF|). Previously, this was known with f being an Ackermann-type function in r and d but not depending on \mathbbF. The novelty of our result is that f has only tower-type dependence on its parameters. It follows from our results that a biased polynomial has low rank; there too we obtain a tower-type dependence improving the previously known Ackermann-type bound.