2026-09-24T21:15:33Zhttps://api.repository.cam.ac.uk/server/oai/request

oai:www.repository.cam.ac.uk:1810/3469792023-12-22T14:00:50Zcom_1810_213747com_1810_256064col_1810_213748

Ranks of tensors and polynomials, with combinatorial applications 10.17863/CAM.94395 Karam, Thomas Gowers, William Timothy 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 F$_{d,R}$ and G$_{d,R}$ such that if an order-d tensor has R-rank at least G$_{d,R}$(l) then we can restrict its entries to a product of sets X$_{1}$ ⨯ … ⨯ X$_{d}$ such that the restriction has R-rank at least l and the sets X$_{1}$,…,X$_{d}$ each have size at most F$_{d,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 X$_{1}$,…,X$_{d}$ 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 F$_{p}$, it is true uniformly in n that if P: F$_{p}^{n}$ → F$_{p}$ is a polynomial with degree at most d such that P(x) is not approximately equidistributed on F$_{p}$ when x is chosen uniformly at random in S$^{n}$, then P coincides on S$^{n}$ 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 F$_{p}$ 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 F$_{p}^{n}$ to F$_{p}$ for some prime p. We show in particular that for every non-empty subset S of F$_{p}$, if for some linear forms φ$_{i}$ on F$_{p}^{n}$ and some subsets E$_{i}$ of F$_{p}$, the set U of all x ∈ S$^{n}$ satisfying all conditions φ$_{i}$(x) ∈ E$_{i}$ is dense inside S$^{n}$ then there exist a bounded number of pairs (θ$_{i}$, T$_{i}$), where the θ$_{i}$ are linear forms on F$_{p}^{n}$ and the T$_{i}$ are subsets of F$_{p}$, such that the set of x ∈ S$^{n}$ satisfying all conditions θ$_{i}$(x) ∈ T$_{i}$ is contained in U and has inside S$^{n}$ approximately the same density as U has inside S$^{n}$. 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. University of Cambridge 2022-09 Thesis Doctoral Doctor of Philosophy (PhD) eng https://www.repository.cam.ac.uk/handle/1810/346979 https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/0cdf4548-9fd8-479c-a0e6-414972625b0e/download fa283d3e5535719e460e98b1f83a34cd https://www.rioxx.net/licenses/all-rights-reserved/ Combinatorics Finite fields Ramsey theory Tensors