pith. sign in

arxiv: 2606.12380 · v1 · pith:VR7Z7JUNnew · submitted 2026-06-10 · 🧮 math.CO

Forbidden Intersection Theorems for Matrix Spaces

Esty Kelman , Nathan Lindzey , Ohad Sheinfeld This is my paper

Pith reviewed 2026-06-27 08:50 UTC · model grok-4.3

classification 🧮 math.CO
keywords forbidden intersectionsmatrix spacesGL(n,q)umvirateshypercontractivityextremal combinatoricslinear algebra over finite fields
0
0 comments X

The pith

The t-umvirates and their duals are the only maximal (t-1)-intersection-free families in GL(n,q) when t is less than a constant times n.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper determines the largest families of invertible n by n matrices over a finite field such that no two differ by a matrix whose kernel has dimension exactly t-1. It proves that whenever t is smaller than some fixed fraction of n, every maximal such family must consist of all invertible matrices that agree on one fixed t-dimensional subspace, or the corresponding family defined via transposes. This matters to a reader because it supplies a complete structural answer to a forbidden-intersection problem in linear algebra, analogous to classical extremal set theory but for matrices. The argument improves an earlier result that required n to be exponentially larger than t, by invoking tail bounds from global hypercontractivity on matrix spaces.

Core claim

We show that the t-umvirates and their duals are the only maximal (t-1)-intersection-free families F subset GL(n,q) for all pairs (n,t) such that t < c n where c is a universal constant. A t-umvirate is the family of all matrices that agree on a fixed t-dimensional subspace, and its dual as those whose transposes agree on it. The result holds for the general linear group over any finite field and extends to any sufficiently dense subclass of matrices.

What carries the argument

The t-umvirate (all invertible matrices agreeing on a fixed t-dimensional subspace) and its dual (the transpose version), which are shown to be maximal (t-1)-intersection-free and the unique such maximal families when t is linearly smaller than n.

If this is right

  • The extremal size is achieved exactly by the t-umvirate constructions for all t below the linear threshold.
  • When t exceeds n/2 the extremal behavior changes and no analogous clean classification is expected.
  • The same hypercontractivity method applies to any sufficiently dense collection of matrices, not only the invertible ones.
  • The prior exponential lower bound on n in terms of t is replaced by a linear one.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The hypercontractivity technique may extend to other linear groups such as SL(n,q) or to matrices over the reals with suitable measures.
  • One could test the result computationally for small n and moderate t to obtain a concrete value for the constant c.
  • Analogous forbidden-kernel-dimension problems may admit similar structural answers in other algebraic settings.

Load-bearing premise

The global hypercontractivity results for matrix spaces apply to the dense subclass of invertible matrices and yield the required tail bounds.

What would settle it

An explicit (t-1)-intersection-free family inside GL(n,q) that is larger than any t-umvirate, or a different maximal family, when t is a small constant fraction of n.

read the original abstract

A family of $m \times n$ matrices $\mathcal{F} \subseteq \mathbb{F}_q^{m \times n}$ is {$(t-1)$-intersection-free} if $\dim \ker(A-B) \neq t-1$ for all $A,B \in \mathcal{F}$. A \emph{forbidden $(t-1)$-intersection problem} for a collection of matrices asks for the size and structure of extremal $(t-1)$-intersection-free families within that collection. We solve this problem in $\mathrm{GL}(n,q)$ for all pairs $(n,t)$ such that $t<c\cdot n$ where $c$ is a universal constant. We show that the $t$-umvirates and their duals, are the only maximal $(t-1)$-intersection-free families $\mathcal{F} \subset \mathrm{GL}(n,q)$. Here, a $t$-umvirate is defined as the family of all matrices that agree on a fixed $t$-dimensional subspace, and its dual as those whose transposes agree on it. The best previously known result, due to Ellis, Kindler, and Lifshitz, established this bound under the assumption $n \geq e^{Ct\log t}$ for some constant $C>0$. We also give Frankl--R\"odl-type constructions showing that this range of $t$ is almost the best possible: we show that for values of $t>n/2$ the extremal behavior changes and no clean analogue is expected. Our proof builds upon recent global hypercontractivity results for matrix spaces due to Evra, Kindler, and Lifshitz, and broadly applies to any sufficiently dense class of matrices.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The manuscript solves the forbidden (t-1)-intersection problem in GL(n,q): a family F subset GL(n,q) is (t-1)-intersection-free if dim ker(A-B) ≠ t-1 for all distinct A,B in F. For all pairs (n,t) with t < c n (universal c>0), it proves that the only maximal such families are the t-umvirates (all invertible matrices agreeing on a fixed t-dimensional subspace) and their duals (those whose transposes agree on the subspace). This improves the prior Ellis-Kindler-Lifshitz result, which required n ≥ exp(C t log t). The proof invokes global hypercontractivity on matrix spaces (Evra-Kindler-Lifshitz) and asserts it applies to any sufficiently dense subclass; Frankl-Rödl-type constructions show the linear range is nearly optimal, as the extremal behavior changes for t > n/2.

Significance. If the central claim holds, the result substantially extends the stability range for intersection theorems from exponential to linear in n, with a clean structural characterization. The broad applicability statement to dense matrix classes and the explicit constructions demonstrating sharpness are strengths. The reliance on external hypercontractivity theorems is standard but makes the density-transfer step load-bearing.

major comments (1)
  1. [Abstract / proof method paragraph] Abstract and proof-method paragraph: the claim that Evra-Kindler-Lifshitz global hypercontractivity on F_q^{n×n} transfers to the dense subclass GL(n,q) (density ρ = |GL(n,q)|/q^{n²} ≈ 1 - O(1/q)) and produces tail bounds on dim ker(A-B) strong enough for stability up to t = Ω(n) with universal c is load-bearing for the main theorem; the dependence of the hypercontractivity parameters (density threshold and tail exponent) on ρ must be stated explicitly, as the abstract asserts applicability but does not display the resulting constants.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and the constructive comment on the abstract and proof-method paragraph. We address the point below.

read point-by-point responses

  1. Referee: [Abstract / proof method paragraph] Abstract and proof-method paragraph: the claim that Evra-Kindler-Lifshitz global hypercontractivity on F_q^{n×n} transfers to the dense subclass GL(n,q) (density ρ = |GL(n,q)|/q^{n²} ≈ 1 - O(1/q)) and produces tail bounds on dim ker(A-B) strong enough for stability up to t = Ω(n) with universal c is load-bearing for the main theorem; the dependence of the hypercontractivity parameters (density threshold and tail exponent) on ρ must be stated explicitly, as the abstract asserts applicability but does not display the resulting constants.

    Authors: We agree that explicitly stating the dependence of the hypercontractivity parameters on the density ρ improves clarity and makes the load-bearing step transparent. The Evra-Kindler-Lifshitz theorem supplies tail bounds whose density threshold and exponent depend on the minimum density δ of the subclass; for GL(n,q) the density ρ equals the n-independent product ∏_{k=1}^∞(1-q^{-k}) which is bounded below by a positive constant depending only on q. This yields tail bounds sufficient for the linear range t=Ω(n) with a constant c=c(ρ)>0 that is universal in n (and hence in the pair (n,t)). In the revised manuscript we will update the abstract and the proof-method paragraph to display this dependence explicitly, for example by adding the clause “with parameters depending on the density threshold ρ, which for GL(n,q) is bounded away from zero uniformly in n.” revision: yes

Circularity Check

0 steps flagged

No circularity; central claim rests on external hypercontractivity theorems

full rationale

The derivation applies the external global hypercontractivity results of Evra-Kindler-Lifshitz (independent authors) to the dense subclass GL(n,q) to obtain tail bounds on dim ker(A-B), then invokes the prior stability result of Ellis-Kindler-Lifshitz to conclude that t-umvirates and duals are the only maximal families for t < c n. No step reduces the target statement to a fitted parameter, self-defined quantity, or self-citation chain; the cited theorems are treated as black-box external inputs whose applicability is asserted without re-deriving them inside the paper. The Frankl-Rödl constructions are separate and do not affect the main stability claim. This is a standard non-circular use of prior theorems.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The proof relies on external hypercontractivity theorems; no new free parameters, ad-hoc axioms, or invented entities are introduced in the abstract.

axioms (1)
  • standard math Standard axioms of linear algebra and finite fields
    Used to define GL(n,q), kernels, and matrix operations throughout.

pith-pipeline@v0.9.1-grok · 5849 in / 1177 out tokens · 24029 ms · 2026-06-27T08:50:32.112235+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

13 extracted references · 10 canonical work pages

  1. [1]

    Polynomial Bogolyubov for special linear groups via tensor rank.arXiv e-prints, page arXiv:2404.00641, March

    [EKL24b] Shai Evra, Guy Kindler, and Noam Lifshitz. Polynomial Bogolyubov for special linear groups via tensor rank.arXiv e-prints, page arXiv:2404.00641, March

    work page arXiv

  2. [2]

    personal communication

    [Ell] David Ellis. personal communication. [Ell22] David Ellis. Intersection problems in extremal combinatorics: theorems, techniques and questions old and new. InSurveys in combinatorics 2022, volume 481 ofLondon Math. Soc. Lecture Note Ser., pages 115–173. Cambridge Univ. Press, Cambridge,

    2022

  3. [3]

    The Hajnal–Rothschild problem, arxiv:2502.06699

    [FK25] Peter Frankl and Andrey Kupavskii. The Hajnal–Rothschild problem, arxiv:2502.06699

    work page arXiv

  4. [4]

    The Erd ˝os-Ko-Rado theorem is true forn=ckt

    [Fra78] Peter Frankl. The Erd ˝os-Ko-Rado theorem is true forn=ckt. InCombinatorics (Proc. Fifth Hun- garian Colloq., Keszthely, 1976), Vol. I, volume 18 ofColloq. Math. Soc. János Bolyai, pages 365–375. North-Holland, Amsterdam-New York,

    1976

  5. [5]

    Forbidding just one intersection for short integer sequences.arXiv preprint arXiv:2512.17544,

    [INST25] Elizaveta Iarovikova, Fedor Noskov, Georgy Sokolov, and Nikolai Terekhov. Forbidding just one intersection for short integer sequences.arXiv preprint arXiv:2512.17544,

    work page arXiv

  6. [6]

    Sharp hypercontractivity for symmetric groups and its applica- tions.arXiv preprint arXiv:2307.15030,

    [KL23] Peter Keevash and Noam Lifshitz. Sharp hypercontractivity for symmetric groups and its applica- tions.arXiv preprint arXiv:2307.15030,

    work page arXiv

  7. [7]

    Forbidden intersections for codes

    FORBIDDEN INTERSECTION THEOREMS FOR MATRIX SPACES 41 [KLLM23] Peter Keevash, Noam Lifshitz, Eoin Long, and Dor Minzer. Forbidden intersections for codes. Journal of the London Mathematical Society, 108(5):2037–2083,

    2037

  8. [8]

    The forbidden cross intersection problem for permutations.arXiv preprint arXiv:2512.11372,

    [KLS25] Nathan Keller, Noam Lifshitz, and Ohad Sheinfeld. The forbidden cross intersection problem for permutations.arXiv preprint arXiv:2512.11372,

    work page arXiv

  9. [9]

    Linear dependencies, polynomial factors in the Duke–Erd ˝os forbidden sunflower problem, arxiv:2410.06156

    [KN24] Andrey Kupavskii and Fedor Noskov. Linear dependencies, polynomial factors in the Duke–Erd ˝os forbidden sunflower problem, arxiv:2410.06156

    work page arXiv

  10. [10]

    Erd ˝os–Ko–Rado type results for partitions via spread approximations,Eur

    [Kup23a] Andrey Kupavskii. Erd ˝os–Ko–Rado type results for partitions via spread approximations,Eur. J. Combin., to appear. arxiv:2309.00097

    work page arXiv

  11. [11]

    Intersection theorems for uniform subfamilies of hereditary families, arxiv:2311.02246

    [Kup23b] Andrey Kupavskii. Intersection theorems for uniform subfamilies of hereditary families, arxiv:2311.02246

    work page arXiv

  12. [12]

    arXiv:2308.08694

    To appear. arXiv:2308.08694. [MZ24] Dor Minzer and Kai Zhe Zheng. Near optimal alphabet-soundness tradeoffpcps. InProceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 15–23,

    work page arXiv

  13. [13]

    Near optimal hardness of approximatingk-csp.arXiv preprint arXiv:2510.23991,

    [MZ25] Dor Minzer and Kai Zhe Zheng. Near optimal hardness of approximatingk-csp.arXiv preprint arXiv:2510.23991,

    work page arXiv