Subspaces of tensors with high analytic rank

Jop Bri\"et

REVIEW 2 major objections 4 minor 16 references

Subspaces of tensors with high analytic rank

T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Every large tensor subspace contains a high-rank core

desk verdict A genuine and clean extension of Meshulam to analytic rank, with a repairable constant slip in the application to random-difference Szemerédi. read the letter →

arxiv 1908.04169 v2 pith:LRLUG27F submitted 2019-08-12 math.CO math.NT

Jop Briët This is my paper · ORCID

classification math.COmath.NT MSC 11B3015A69

keywords analyticranktensorsoverfinitefieldssubspaceofMeshulamtheoremSzemerédiwithrandomdifferencesarithmeticprogressionsbiaspartition

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper proves a tensor analogue of a classical matrix theorem: any subspace of $d$-tensors over a finite field with dimension at least $t n^{d-1}$ contains a subspace of dimension at least $\frac{t}{dr}-1$ all of whose nonzero elements have analytic rank at least $c r$, for a constant $c$ depending only on the field and $d$. Analytic rank, the negative logarithm of the bias of a tensor, is the natural tensor analogue of matrix rank and controls how uniformly a tensor behaves on random inputs. The proof is a careful Meshulam-style coordinate-picking argument using monotonicity of analytic rank under restrictions. The theorem's payoff is a new lower bound for Szemerédi's theorem with random differences: if too few common differences are sampled in $\mathbb{F}_p^n$, a positive-density set can avoid all proper $k$-term arithmetic progressions with those differences, extending a known result from $k=3$ to every $k$.

What carries the argument

The mechanism is the bias--analytic-rank pair. For a $d$-tensor $T$, bias is $\mathrm{bias}(T)=\mathbb{E}_{x_1,\dots,x_d\in F^n}\chi(T(x_1,\dots,x_d))$ for a nontrivial additive character $\chi$, and analytic rank is $-\log_{|F|}\mathrm{bias}(T)$; for $d=2$ this is the usual matrix rank, and low analytic rank means the tensor is close to uniform on random inputs. The proof arranges a basis so its leading coordinates are distinct, covers the coordinate grid by at most $d n^{d-1}$ diagonal matchings, and picks $rs$ basis elements whose pivots lie on one matching. Restricting to the $r\times\cdots\times r$ boxes these pivots span, it builds, one pivot at a time, tensors whose restriction gains at least a fixed amount $c_{F,d}$ of analytic rank at each step; the induction step is powered by a corollary of an averaging lemma for bias, stated as Lemma 2.3 of [Lov19]. The final subspace is spanned by these independently constructed high-rank pieces.

What would settle it

For $d=3$ over $\mathbb{F}_3$, run the construction in the proof of Theorem 1.3 on a $t n^2$-dimensional subspace and compute the dimension $m$ of $W$ and the minimum analytic rank among its nonzero elements; if $m<8t$ or the rank is below $8t$, Proposition 3.3's advertised $2/p^{2t}$ bound does not follow from the written argument. Independently, test the imported diagonal-bias estimate on random symmetric tensors of analytic rank $r=2dt$; a counterexample there would also break the application.

Watch

Extended reading notes

Core claim

The central claim, stated as Theorem 1.3, is that for every finite field $F$ and integer $d\ge 2$ there is a constant $c=c_{F,d}\in(0,1]$ such that whenever $V\subseteq F^{n\times\cdots\times n}$ is a subspace of $d$-tensors with $\dim(V)\ge t n^{d-1}$, there exists a subspace $W\subseteq V$ with $\dim(W)\ge \frac{t}{dr}-1$ such that every nonzero $T\in W$ has $\mathrm{arank}(T)\ge c r$. The theorem simultaneously sharpens Meshulam's rank theorem to tensors and is close to tight: the subspace $U\otimes F^{n\times\cdots\times n}$ built from a $t$-dimensional $U\subseteq F^n$ has dimension $t n^{d-1}$ and contains only tensors of analytic rank at most $t$. Because partition rank dominates analytic rank, the same conclusion transfers to partition rank, and the known polynomial comparison shows the parameters cannot be far from optimal.

Load-bearing premise

The load-bearing premise is that the subspace $W$ produced by Theorem 1.3 has dimension and analytic rank at least $2^d t$; the theorem as written guarantees only $2dt$, and the probability bound in Proposition 3.3 also depends on a diagonal-bias estimate imported from [Alt19] that is not proved in the present paper.

Editorial extensions

If this is right

A subspace of $d$-tensors of dimension at least $r n^{d-1}$ must contain a single tensor of analytic rank $\Omega_{d,p}(r)$, matching the form of Meshulam's matrix-rank theorem.
The same high-rank-subspace conclusion holds for partition rank, since partition rank dominates analytic rank, so the subspace $W$ is automatically high-rank in both senses.
The parameters are essentially optimal: a tensor product construction gives a $t n^{d-1}$-dimensional subspace whose nonzero elements all have analytic and partition rank at most $t$.
For random common differences in $\mathbb{F}_p^n$, sampling at most $\binom{n+k-2}{k-1}-C(\log_p n)^2 n^{k-2}$ differences leaves, with probability $1-o(1)$, a set $A$ of density $\Omega_{k,p}(1)$ that contains no proper $k$-term arithmetic progression with common difference in $S$.
Consequently at least $\Omega((\log_p N)^{k-1})$ sampled differences are necessary for Szemerédi's theorem with random differences over $\mathbb{F}_p^n$, generalizing the known $k=3$ obstruction to all $k\ge 3$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The diagonal-matching cover is the only place where the $n^{d-1}$ exponent enters, so the same greedy argument should carry over to rectangular tensors with leg lengths $n_1,\dots,n_d$, replacing $n^{d-1}$ by the product of the largest $d-1$ leg lengths.
If the quantitative gap in Proposition 3.3 can be absorbed by a larger constant, the same high-rank-subspace mechanism might yield random-difference lower bounds in non-abelian groups, where the missing ingredient is a non-abelian analogue of the imported diagonal-bias estimate.
A testable route around the imported diagonal-bias lemma is to prove the analogue of Proposition 3.3 for independent vectors $x_1\otimes\cdots\otimes x_d$ rather than the diagonal $\phi_d(x)$; the restriction machinery of the proof appears to give this directly.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The main result is real and new: for a subspace of d-tensors over a finite field, dimension at least t n^{d-1} forces a large subspace whose nonzero elements all have analytic rank at least c r. The proof adapts Meshulam's diagonal-matching argument, uses Lovett's inequalities, and avoids partition rank entirely. That is a genuine contribution in higher-order Fourier analysis, and the application to random-difference Szemerédi for all k (generalizing Altman's k=3) is a natural payoff. The proof of Theorem 1.3 itself is rigorous, with explicit constants, and I do not see a hidden circularity.

The soft spot is exactly where your stress-test lands: Proposition 3.3. The written proof claims that Theorem 1.3 yields a subspace W with dimension m ≥ 2dt and every nonzero element of analytic rank at least r ≥ 2dt, and then uses those inequalities to bound the average bias. But the final bound needs m,r ≥ 2^d t, not 2dt; for d ≥ 3 the p-exponent after the (2^{d-1})-th root is too small. This is a constant bookkeeping error, not a structural one—the free constant C can easily absorb the extra factor. Still, the paper as written is incomplete at that point, and a referee would need the author to fix the thresholds and spell out the choice of C.

A second, smaller issue: the proof cites [Alt19, Lemma 3.5] for the inequality bounding the diagonal expectation by a power of the average bias. That lemma is not stated, and its hypotheses (in particular whether it applies to symmetric d-tensor subspaces for all d and for p ≥ d+1) should be made explicit. A reader should not have to chase down the reference to verify a load-bearing step.

The rest of the paper is clean and to the point. The connection to partition rank is handled correctly, and the parameters are close to optimal via the tensor product construction. This deserves a serious referee; the main theorem is solid and the application is interesting, but the paper does need minor revision. I would send it out with a request to fix Proposition 3.3 and state the Altman lemma.

For a reading group: worth it if anyone works in analytic rank or random-difference Szemerédi. I would cite it if I were writing in that area.

Referee Report

2 major / 4 minor

Summary. The paper proves a tensor analogue of Meshulam's theorem: for any finite field F, integer d ≥ 2, and subspace V of d-tensors over F with dim(V) ≥ t n^{d-1}, there is a subspace W ⊆ V of dimension at least t/(dr) − 1 such that every nonzero element of W has analytic rank at least c r, where c depends only on F and d. The proof follows Meshulam's diagonal-matching strategy and uses Lovett's analytic-rank lemmas. As an application, the author obtains a lower bound for Szemerédi's theorem with random differences in F_p^n, generalizing Altman's result from 3-term to arbitrary k-term arithmetic progressions.

Significance. The main theorem is a clean and natural extension of Meshulam's linear-algebra result to higher-order tensors, and the analytic rank is the right notion for the application. The proof of Theorem 1.3 is a genuine derivation from Lovett's lemmas and is internally sound; the diagonal-matching argument is elegant and self-contained apart from the cited lemmas. The application to random differences is interesting and gives the first such lower bound for all k. The paper is concise and well organized. The main caveat is that Proposition 3.3, which is load-bearing for the application, has a repairable but real gap in its final estimate, and one of its cited ingredients is not stated with its hypotheses.

major comments (2)

[3, Proposition 3.3, proof] The final chain of inequalities in Proposition 3.3 is not justified by the stated bounds m,r ≥ 2dt. From the displayed bound, the average bias is at most (1/p^m + (p^m−1)/p^m · 1/p^r) ≤ 2/p^{2dt}, so after taking the (2^{d−1})-th root one obtains 2^{1/2^{d−1}}/p^{2dt/2^{d−1}}. For d ≥ 3, the exponent 2dt/2^{d−1} is strictly smaller than 2t (for d = 3 it equals 3t/2), so the final inequality ≤ 2/p^{2t} fails for large t. This is fixable by choosing m and r to be at least 2^d t (or a sufficiently large constant multiple), which the free constant C in Proposition 3.3 can absorb by taking the dimension threshold in Theorem 1.3 large enough; however, as written the proof is incomplete and the application of Theorem 1.3 to force m,r ≥ 2dt should be revisited to obtain the stronger bounds.
[3, Proposition 3.3, proof] The first inequality in the displayed chain, Ex∈F_p^n ET∈W ω^{⟨φ_d(x),T⟩} ≤ (ET∈W bias(T))^{1/2^{d−1}}, is cited to [Alt19, Lemma 3.5] without stating the lemma or its hypotheses. This is a load-bearing step for the proposition, which is stated for all d ≥ 2 and p ≥ d+1 over symmetric tensor subspaces. The author should quote the lemma (or give a proof) and confirm that its hypotheses cover exactly this setting; as it stands, the reader cannot verify that the cited result applies.

minor comments (4)

[2, Corollary 2.4 proof] In the proof of Corollary 2.4, the displayed expectations use v1,...,v_n ∈ V and u1,...,u_n ∈ U; these should be v1,...,v_d ∈ V and u1,...,u_d ∈ U, since d is the order of the tensor.
[2, Corollary 2.4 proof] In the same proof, the notation Eu1,...,un∈U appears twice where the subscript should be u1,...,ud∈U; this is a typographical slip but could confuse the reader about the number of variables.
[2, Proof of Theorem 1.3] The sentence 'Since the sets Ij are pairwise disjoint and the tensors T1,...,Tdim(V) are linearly independent, it follows that dim(W) ≥ s' is correct, but a brief justification that the T_j^* are linearly independent because their leading coordinates lie in disjoint blocks would make the argument easier to follow.
[1, Introduction] The statement 'for any d ≥ 2, the analytic rank is at most n' is used implicitly; a short proof or explicit reference would be helpful, since it is not immediate from the definition.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: all load-bearing inputs are external (Lovett, Gowers–Wolf, Altman) and the main theorem is proved by a genuine construction.

full rationale

The paper's central result, Theorem 1.3, is proved directly via Gaussian elimination, a diagonal-matching cover, and two externally cited lemmas of Lovett (Lemmas 2.1 and 2.3). The only internal citations to the author's own prior work ([BG18], [BDG19]) appear in the introduction as background on the random-differences problem and are not used in any proof. The analytic-rank construction in Theorem 1.3 uses no fitted parameters and no hypothesis equivalent to its conclusion. The application in Theorem 1.5 is a genuine derivation: it combines Theorem 1.3 with Altman's external Lemma 3.1, the Chevalley–Warning theorem, and the random-bias estimate from Proposition 3.3, whose probabilistic bound is ultimately justified by Lovett's and Gowers–Wolf's external results. The known concern about Proposition 3.3 is a quantitative gap — the stated conditions m, r ≥ 2dt do not obviously yield the final p^{-2t} bound — but this is a correctness issue, not circularity, and it does not make any claimed derivation equivalent to its inputs. No self-definitional, fitted-prediction, or self-citation-load-bearing pattern is present.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The central results rest on standard external lemmas from Lovett, Gowers-Wolf, and Altman, all cited in the paper. No ad hoc free parameters or invented entities are introduced; the constants are existential and can be chosen large enough to satisfy the inequalities, provided the constant bookkeeping in Proposition 3.3 is repaired.

assumptions (6)

standard math Lovett's Lemma 2.1: analytic rank is monotone under restriction to principal sub-tensors.
Used in Corollary 2.2 and at the end of the proof of Theorem 1.3 to pass from a tensor to its restriction.
standard math Lovett's Lemma 2.3: the bias of a tensor contracted on a subspace is at most the bias of the unrestricted restriction.
Used in Corollary 2.4 to show that adding a coordinate can increase analytic rank by a constant.
standard math Gowers-Wolf Lemma 3.2 and Altman's Lemma 3.5: the diagonal expectation of a tensor phase is bounded by a power of the average analytic bias.
Used in Proposition 3.3 to upper bound the probability that a random symmetric tensor lies in a subspace.
domain assumption Altman's Lemma 3.1: if the set of rank-one tensors φ_{k-1}(S) is linearly independent, then a tensor exists whose zero set avoids k-APs with differences in S.
Used directly in the proof of Theorem 1.5 to construct the set A.
standard math Chevalley-Warning theorem: a system of polynomial equations over a finite field has many solutions if the number of variables exceeds the sum of degrees.
Used to lower bound the size of the zero set A in Theorem 1.5.
domain assumption The inner product on symmetric tensors is non-degenerate when p > d.
Used in Proposition 3.3 to identify the orthogonal complement of a subspace of symmetric tensors.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Subspaces of tensors with high analytic rank." pith.science (2026). https://pith.science/paper/LRLUG27F

@misc{pith2026190804169,
  author       = {Pith},
  title        = {Pith review of: Subspaces of tensors with high analytic rank},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LRLUG27F}},
  note         = {Machine review of arXiv:1908.04169}
}

abstract

It is shown that for any subspace $V\subseteq \mathbb{F}_p^{n\times\cdots\times n}$ of $d$-tensors, if $\dim(V) \geq tn^{d-1}$, then there is subspace $W\subseteq V$ of dimension at least $t/(dr) - 1$ whose nonzero elements all have analytic rank $\Omega_{d,p}(r)$. As an application, we generalize a result of Altman on Szemer\'edi's theorem with random differences.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

16 extracted references · 14 canonical work pages

[1]

D. Altman. On S zemer\'edi's theorem with differences from a random set. Acta Arith, 2019. To appear. ArXiv:1905.05045

work page Pith review arXiv 2019
[2]

Bri\" e t, Z

J. Bri\" e t, Z. Dvir, and S. Gopi. Outlaw distributions and locally decodable codes. Theory of Computing, 15(12):1--24, 2019. doi:10.4086/toc.2019.v015a012. Preliminary version in ITCS'17

work page doi:10.4086/toc.2019.v015a012 2019
[3]

Bri \"e t and S

J. Bri \"e t and S. Gopi. Gaussian width bounds with applications to arithmetic progressions in random settings. International Mathematics Research Notices, page rny238, 2018. doi:10.1093/imrn/rny238

work page doi:10.1093/imrn/rny238 2018
[4]

On Multilinear Forms: Bias, Correlation, and Tensor Rank

A. Bhrushundi, P. Harsha, P. Hatami, S. Kopparty, and M. Kumar. On multilinear forms: Bias, correlation, and tensor rank, 2018. ArXiv: 1804.09124

work page Pith review arXiv 2018
[5]

M. Christ. On random multilinear operator inequalities. arXiv: 1108.5655, 2011

arXiv 2011
[6]

Frantzikinakis, E

N. Frantzikinakis, E. Lesigne, and M. Wierdl. Random sequences and pointwise convergence of multiple ergodic averages. Indiana Univ. Math. J., 61(2):585--617, 2012. doi:10.1512/iumj.2012.61.4571

work page doi:10.1512/iumj.2012.61.4571 2012
[7]

Frantzikinakis, E

N. Frantzikinakis, E. Lesigne, and M. Wierdl. Random differences in S zemer \'e di's theorem and related results. J. Anal. Math., 130:91--133, 2016. doi:10.1007/s11854-016-0030-z

work page doi:10.1007/s11854-016-0030-z 2016
[8]

W. T. Gowers and J. Wolf. Linear forms and higher-degree uniformity for functions on F^n_p . Geom. Funct. Anal., 21(1):36--69, 2011. doi:10.1007/s00039-010-0106-3

work page doi:10.1007/s00039-010-0106-3 2011

Show all 16 references

[9]

O. Janzer. Polynomial bound for the partition rank vs the analytic rank of tensors, 2019. ArXiv:1902.11207

2019 arXiv
[10]

Kazhdan and T

D. Kazhdan and T. Ziegler. Approximate cohomology. Selecta Math. (N.S.), 24(1):499--509, 2018. doi:10.1007/s00029-017-0335-5

2018 doi
[11]

Lidl and H

R. Lidl and H. Niederreiter. Finite Fields, volume 20 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, second edition, 1997. With a foreword by P. M. Cohn

1997
[12]

S. Lovett. The analytic rank of tensors and its applications. Discrete Anal., pages 1--10, 2019. doi:10.19086/da.8654. Paper No. 7

2019 doi
[13]

Meshulam

R. Meshulam. On the maximal rank in a subspace of matrices. The Quarterly Journal of Mathematics, 36(2):225--229, 1985. doi:10.1093/qmath/36.2.225

1985 doi
[14]

Mili \'c evi \'c

L. Mili \'c evi \'c . Polynomial bound for partition rank in terms of analytic rank. Geom. Funct. Anal., 29(5):1503--1530, 2019. doi:10.1007/s00039-019-00505-4

2019 doi
[15]

E. Naslund. The partition rank of a tensor and k -right corners in F _q^n , 2017. ArXiv:1701.04475

2017 arXiv
[16]

Szemer \'e di

E. Szemer \'e di. On sets of integers containing no k elements in arithmetic progression. Acta Arith., 27:199--245, 1975. doi:10.4064/aa-27-1-199-245

1975 doi

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

D. Altman. On S zemer\'edi's theorem with differences from a random set. Acta Arith, 2019. To appear. ArXiv:1905.05045

work page Pith review arXiv 2019

[2] [2]

Bri\" e t, Z

J. Bri\" e t, Z. Dvir, and S. Gopi. Outlaw distributions and locally decodable codes. Theory of Computing, 15(12):1--24, 2019. doi:10.4086/toc.2019.v015a012. Preliminary version in ITCS'17

work page doi:10.4086/toc.2019.v015a012 2019

[3] [3]

Bri \"e t and S

J. Bri \"e t and S. Gopi. Gaussian width bounds with applications to arithmetic progressions in random settings. International Mathematics Research Notices, page rny238, 2018. doi:10.1093/imrn/rny238

work page doi:10.1093/imrn/rny238 2018

[4] [4]

On Multilinear Forms: Bias, Correlation, and Tensor Rank

A. Bhrushundi, P. Harsha, P. Hatami, S. Kopparty, and M. Kumar. On multilinear forms: Bias, correlation, and tensor rank, 2018. ArXiv: 1804.09124

work page Pith review arXiv 2018

[5] [5]

M. Christ. On random multilinear operator inequalities. arXiv: 1108.5655, 2011

arXiv 2011

[6] [6]

Frantzikinakis, E

N. Frantzikinakis, E. Lesigne, and M. Wierdl. Random sequences and pointwise convergence of multiple ergodic averages. Indiana Univ. Math. J., 61(2):585--617, 2012. doi:10.1512/iumj.2012.61.4571

work page doi:10.1512/iumj.2012.61.4571 2012

[7] [7]

Frantzikinakis, E

N. Frantzikinakis, E. Lesigne, and M. Wierdl. Random differences in S zemer \'e di's theorem and related results. J. Anal. Math., 130:91--133, 2016. doi:10.1007/s11854-016-0030-z

work page doi:10.1007/s11854-016-0030-z 2016

[8] [8]

W. T. Gowers and J. Wolf. Linear forms and higher-degree uniformity for functions on F^n_p . Geom. Funct. Anal., 21(1):36--69, 2011. doi:10.1007/s00039-010-0106-3

work page doi:10.1007/s00039-010-0106-3 2011