{"id":{"repo_id":"cambridge","oai_identifier":"oai:www.repository.cam.ac.uk:1810/346979"},"canonical_url":"https://search.dev.ndltd.org/etd/cambridge/oai:www.repository.cam.ac.uk:1810/346979","repository":{"repo_id":"cambridge","name":"Cambridge University","base_url":"https://api.repository.cam.ac.uk/server/oai/request"},"display":{"title":"Ranks of tensors and polynomials, with combinatorial applications","abstract":"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.","abstract_html":"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.","abstract_has_math":true,"creators":["Karam, Thomas"],"institution":"University of Cambridge","degree_name":"Doctor of Philosophy (PhD)","degree_level":"Doctoral","degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":["Gowers, William Timothy"],"committee_chairs":[],"committee_members":[],"year":2022,"date_issued":"2022-09","date_published":"2022-09","updated_at":"2026-07-22T22:24:20Z","subjects":["Combinatorics","Finite fields","Ramsey theory","Tensors"],"languages":["eng"],"rights":[],"rights_urls":["https://www.rioxx.net/licenses/all-rights-reserved/"],"identifier_entries":[]},"links":{"outbound_url":"https://doi.org/10.17863/CAM.94395","outbound_label":"DOI","outbound_source":"dc:identifier.doi"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Gowers, William Timothy"]},{"key":"dc:creator","label":"Author","values":["Karam, Thomas"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.issued","label":"Date","values":["2022-09"]},{"key":"dc:publisher.institution","label":"Dc Publisher Institution","values":["University of Cambridge"]},{"key":"dc:relation.isreferencedby.uri","label":"Dc Relation Isreferencedby URI","values":["https://www.repository.cam.ac.uk/handle/1810/346979"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"dc:type.qualificationlevel","label":"Dc Type Qualificationlevel","values":["Doctoral"]},{"key":"dc:type.qualificationname","label":"Dc Type Qualificationname","values":["Doctor of Philosophy (PhD)"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Combinatorics","Finite fields","Ramsey theory","Tensors"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["https://www.rioxx.net/licenses/all-rights-reserved/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.doi","label":"DOI","values":["10.17863/CAM.94395"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/0cdf4548-9fd8-479c-a0e6-414972625b0e/download"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:format.checksum.md5","label":"Dc Format Checksum Md5","values":["fa283d3e5535719e460e98b1f83a34cd"]},{"key":"dc:title","label":"Title","values":["Ranks of tensors and polynomials, with combinatorial applications"]}]}],"canonical_facts":{"dc:contributor.advisor":["Gowers, William Timothy"],"dc:creator":["Karam, Thomas"],"dc:date.issued":["2022-09"],"dc:description.abstract":["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."],"dc:format.checksum.md5":["fa283d3e5535719e460e98b1f83a34cd"],"dc:identifier.doi":["10.17863/CAM.94395"],"dc:identifier.uri":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/0cdf4548-9fd8-479c-a0e6-414972625b0e/download"],"dc:language":["eng"],"dc:publisher.institution":["University of Cambridge"],"dc:relation.isreferencedby.uri":["https://www.repository.cam.ac.uk/handle/1810/346979"],"dc:rights":["https://www.rioxx.net/licenses/all-rights-reserved/"],"dc:subject":["Combinatorics","Finite fields","Ramsey theory","Tensors"],"dc:title":["Ranks of tensors and polynomials, with combinatorial applications"],"dc:type":["Thesis"],"dc:type.qualificationlevel":["Doctoral"],"dc:type.qualificationname":["Doctor of Philosophy (PhD)"]},"updated_at":"2026-07-22T22:24:20Z"}