Repository logo

Ranks of tensors and polynomials, with combinatorial applications



Change log


Karam, Thomas 


This thesis will consist of three main chapters.

It is a standard fact of linear algebra that every matrix with rank k contains a k ⨯ k submatrix with rank k. In Chapter 2 we generalise this fact asymptotically to a class of notions of rank for higher-order tensors, containing in particular the tensor rank, the slice rank and the partition rank. We show that for every integer d ⩾ 2 and every notion R in this class of notions of rank, there exist functions Fd,R and Gd,R such that if an order-d tensor has R-rank at least Gd,R(l) then we can restrict its entries to a product of sets X1 ⨯ … ⨯ Xd such that the restriction has R-rank at least l and the sets X1,…,Xd each have size at most Fd,R(l). Combining the proof methods that we use to prove this result with a few additional ideas then allows us to show that under a very natural condition we can furthermore require the sets X1,…,Xd to be pairwise disjoint.

In Chapter 3 we extend to the case of restricted subsets a result of Green and Tao on the equidistribution of high-rank polynomials over finite prime fields. We show that for every fixed prime integer p, for every integer d ∈ [2, p-1], and for every non-empty subset S of Fp, it is true uniformly in n that if P: Fpn → Fp is a polynomial with degree at most d such that P(x) is not approximately equidistributed on Fp when x is chosen uniformly at random in Sn, then P coincides on Sn with a polynomial which can be expressed as a function of a bounded number of polynomials of degree at most d-1. Our argument uses two results which are known by that point: the second main result of Chapter 2, and the fact that an order-d tensor over Fp with high partition rank necessarily has high analytic rank.

In Chapter 4 we prove approximation results for conditions on {0,1}n and similar sets when those conditions are defined using polynomials from Fpn to Fp for some prime p. We show in particular that for every non-empty subset S of Fp, if for some linear forms φi on Fpn and some subsets Ei of Fp, the set U of all x ∈ Sn satisfying all conditions φi(x) ∈ Ei is dense inside Sn then there exist a bounded number of pairs (θi, Ti), where the θi are linear forms on Fpn and the Ti are subsets of Fp, such that the set of x ∈ Sn satisfying all conditions θi(x) ∈ Ti is contained in U and has inside Sn approximately the same density as U has inside Sn. As an application, we rule out a class of potential counterexamples to a first unsolved case of the polynomial density Hales-Jewett conjecture. We also generalise our approximation results in some other directions: in particular we deduce an approximation result (with a weaker formulation) for polynomials of small degree from the main result of Chapter 3.





Gowers, William Timothy


Combinatorics, Finite fields, Ramsey theory, Tensors


Doctor of Philosophy (PhD)

Awarding Institution

University of Cambridge