Pith. sign in

REVIEW 2 major objections 5 minor 44 references

Quantitative invertibility of random matrices: a combinatorial perspective

T0 review · 2 major / 5 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 Exponential invertibility bounds for smoothed random matrices

desk verdict A genuinely new combinatorial approach to smoothed least-singular-value bounds, with strong results and one nontrivial formal gap: Theorem 1.3 as stated forbids the prime p used later in the proof. read the letter →

arxiv 1908.11255 v3 pith:B4JNFI6W submitted 2019-08-29 math.PR cs.NAmath.COmath.NA

Vishesh Jain This is my paper · ORCID
classification math.PRcs.NAmath.COmath.NA MSC 60B2015B52
keywords leastsingularvaluesmoothedanalysisrandommatricessmall-ballprobabilityGaussianintegervectorscombinatorialcountingsingularity
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

The paper proves a quantitative lower-tail bound for the least singular value of an $n\times n$ smoothed random matrix $M_n=M+N_n$: $M$ may be any fixed complex matrix with operator norm at most $2^{n^{0.001}}$, and $N_n$ has independent entries with mean 0 and variance 1. For any failure probability $\alpha\ge 2^{-n^{0.001}}$, it shows $\Pr(s_n(M_n)\le\eta)\le C\alpha$ for all sufficiently small $\eta$, with $C$ depending only on the entry distribution. This extends earlier smoothed-analysis estimates, which applied only to polynomially bounded $M$, and it upgrades the singularity probability from inverse-polynomial to exponentially small in a power of $n$ even for polynomially bounded $M$. The proof avoids inverse small-ball structure theorems and net constructions; instead it reduces the problem to counting Gaussian integer vectors and solves that counting problem by a combinatorial method over finite fields.

What carries the argument

The central object is the counting variant of the inverse small-ball problem. For Gaussian integer vectors $v\in(\mathbb Z+i\mathbb Z)^n$ whose Levy concentration function (the maximum probability that $\sum v_i\xi_i$ falls in a small ball) is at least $\rho$, Theorem 1.3 bounds the number of distinct vectors after reduction modulo a prime $p$ by $(5np^2/s)^s+(C_{1.3}\rho^{-1}\sqrt{s/k})^n$, provided $\rho\ge C_{1.3}\max\{e^{-s/k},s^{-k/4}\}$. This counting bound carries the argument: rich unit vectors are rescaled until they nearly coincide with Gaussian integer vectors, Proposition 2.8 converts any Euclidean distance from the Gaussian integer lattice into exponential decay of the concentration function, and Proposition 4.16 bounds the number of approximating integer vectors in each scale class. The proof of Theorem 1.3 itself combines a Fourier anti-concentration step, sumset growth over $\mathbb F_p+i\mathbb F_p$, and a double-counting lemma (Theorem 5.4) that controls vectors admitting many balanced sign relations.

What would settle it

Set $\xi$ to Bernoulli and $M$ to a fixed $n\times n$ complex matrix with $\|M\|=2^{n^{0.001}}$, choose $\alpha=2^{-n^{0.001}}$, and compute $\Pr(s_n(M_n)\le\eta)$ for $\eta$ at the threshold stated in Theorem 1.1; exceeding $C_{1.1}\alpha$ would refute the theorem. A sharper falsifier targets Theorem 1.3 directly: take $s=n^{0.9}$, $k=n^{0.1}$, $p=2^{n^{0.04}}$, and $\rho=2^{-\ell}/(128n^{0.30})$ for $\ell\le\log(\beta^{-1})$, and check whether some collection $V^\rho$ has more than $(5np^2/s)^s+(C\rho^{-1}\sqrt{s/k})^n$ distinct images under the mod-$p$ map.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is Theorem 1.1: for any complex random variable with mean 0 and variance 1, any fixed complex matrix $M$ with $\|M\|\le 2^{n^{0.001}}$, and any $\alpha\ge 2^{-n^{0.001}}$, the least singular value of $M_n=M+N_n$ satisfies $\Pr(s_n(M_n)\le\eta)\le C_{1.1}\alpha$ whenever $\eta\le (C_{1.1}(\|M\|+\sqrt n)\alpha^{-1}n^2)^{-300\log(\alpha^{-1})/\log n}$. The same result recovers the earlier polynomial-$M$ bounds while broadening the valid range of $\|M\|$ to exponential in a small power of $n$, and it yields exponential-type bounds on the probability that a perturbed matrix is singular. The paper also isolates Theorem 1.3, a counting estimate for vectors whose small-ball probability is at least $\rho$, as the key new tool; this estimate extends the combinatorial counting approach to arbitrary complex random variables and may stand on its own.

Load-bearing premise

The load-bearing premise is that the number of Gaussian integer vectors with small-ball probability at least $\rho$ stays exponentially small after reduction modulo a prime, in the precise sense of Theorem 1.3; if the true count were even slightly larger, the union bound over approximating rich vectors in Proposition 4.16 would fail and the main theorem would not follow.

Editorial extensions

If this is right

  • Any fixed matrix with operator norm up to $2^{n^{0.001}}$ is, after an independent variance-one perturbation, invertible with least singular value at least $\eta$ except with probability $C\alpha$; in particular, smoothed-analysis guarantees now cover exponentially large input matrices.
  • For polynomially bounded $M$, the probability that $M_n$ is singular is at most $C2^{-n^{0.001}}$ up to the constant, so a random perturbation destroys exact singularity with exponentially high confidence.
  • Theorem 1.3 supplies a general complex-variable counting estimate for vectors with large small-ball probability, with no dependence on structural inverse theorems; it can be used as a drop-in tool in other union-bound arguments.
  • The proof demonstrates that the quantitative invertibility problem for smoothed random matrices can be solved through the discrete counting problem alone, without metric entropy nets or additive-combinatorial structure theory.

Reading between the lines

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

  • A natural extension is to push the norm bound beyond $2^{n^{0.001}}$: the paper notes the exponent is arbitrary, so one would expect the same reduction to work for $\|M\|\le 2^{n^{c}}$ with any fixed $c<1$, at the cost of a worse dependence of $\eta$ on $\alpha$ and $\|M\|$.
  • The same rich-vector counting scheme might be coupled with existing geometric net arguments to yield typical-order bounds, for instance $\eta\sim n^{-1/2}$, for heavy-tailed or dependent-coordinate complex entries, a regime the current theorem does not address.
  • Because the proof reduces the problem to the size of $V^\rho$ modulo $p$, a numerical enumeration of Gaussian integer vectors for moderate $n$ could directly test the counting estimate in Theorem 1.3 before the full theorem is invoked.
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.

Referee Report

2 major / 5 minor

Summary. The paper studies the lower tail of the smallest singular value of an n-by-n matrix M_n = M + N_n, where M is a fixed complex matrix and N_n has i.i.d. entries distributed as an arbitrary complex random variable with mean 0 and variance 1. The main result, Theorem 1.1, gives Pr(s_n(M_n) <= eta) <= C_1.1 alpha for alpha as small as exp(-n^0.001) and for M with ||M|| <= exp(n^0.001), with eta subject to a quantitative upper bound. This improves on the Tao--Vu smoothed-analysis estimates in the allowed size of M and in the error probability. The proof avoids inverse Littlewood--Offord theorems and avoids serious net constructions; instead, it reduces the problem to counting Gaussian integer vectors near rich vectors and proves a counting theorem, Theorem 1.3, for general complex random variables. A subgaussian warm-up is given in Section 3, the general reduction in Section 4, and the proof of Theorem 1.3 in Section 5.

Significance. If the proof is correct, the paper is a substantial advance: it extends the smoothed-analysis regime for the least singular value from polynomial ||M|| to exponentially large ||M||, gives a probability bound exp(-n^c)-style even for Bernoulli noise, and provides a combinatorial route that avoids both inverse Littlewood--Offord structure theorems and nets. The extension of the counting problem in inverse Littlewood--Offord theory to general complex random variables (Theorem 1.3) is a useful contribution in its own right. The paper is clearly written and the reduction from the complex sphere to Gaussian integer vectors is a genuinely different approach. However, as detailed below, there is a load-bearing mismatch between the statement of Theorem 1.3 and its application, and a related gap in the proof of Theorem 1.3 for part of its stated range.

major comments (2)
  1. [Section 5, Step 4, after Eq. (8)] The application of Theorem 1.3 is outside the stated hypotheses. In Proposition 3.15 (and the same calculation used in Proposition 4.16), Theorem 1.3 is applied with s = n^0.9, k = n^0.1, and p = 2^{n^0.04}. The theorem as stated requires 2n/s >= p, but 2n/s = 2n^0.1, so p is exponentially larger than the permitted value. This is not a cosmetic issue: the proof immediately uses the large choice of p to assert that phi_p is injective on the approximating integer vectors, whose coordinates are bounded by about 2^{n^0.01} (see Proposition 4.16) or 2^{n^0.04} (Proposition 3.15). If one respected the stated upper bound and chose p <= 2n^0.1, the reduction map would not be injective on those vectors, and the counting bound on phi_p(V^rho) would not transfer back to R_{j,ell}(beta). The proof of Theorem 1.3 in Section 5 appears not to use the upper bound p <= 2n/s, which suggests that the upper bound in the statement may be a typo, but as written the main proof relies on applying a theorem outside its hypotheses. The authors should either remove or correct the upper-bound hypothesis in Theorem 1.3 and verify that the proof of Section 5 still goes through, or supply an alternative argument that permits the large p needed for injectivity.
  2. [Section 5, Step 4, after Eq. (8)] In the proof of Theorem 1.3, the displayed chain deduces |P'_M(I)| >> sqrt(M/m0)(|P'_m0(I)| - p) directly from the inequality |P'_{t^2 m}(I)| >= min{p^2, t|P'_m(I)| - tp}. This deduction is valid only when the un-truncated quantity does not exceed p^2; otherwise the minimum forces |P'_M(I)| = p^2, which can be smaller than the displayed lower bound. In terms of the later lower bound |P'_M(I)| >> sqrt(M) rho exp(m0/16) p^2, the missing condition is essentially rho sqrt(M) = O(1). This condition is not included in the hypotheses of Theorem 1.3, so the theorem as stated is not proved for all allowed rho (e.g. rho close to 1). The applications in the present paper satisfy rho sqrt(M) << 1 automatically, so this gap does not by itself invalidate Theorem 1.1, but the statement and proof of Theorem 1.3 need to be reconciled.
minor comments (5)
  1. [Section 5, Step 4] The Cauchy--Davenport theorem for F_p + iF_p is cited as '[?]'; a concrete reference is needed.
  2. [Section 3, Proposition 3.7] The proof of Proposition 3.7 is omitted with a pointer to Proposition 4.7; this is acceptable for a warm-up, but the text should state explicitly that Proposition 4.7 is the complete proof in the general case.
  3. [Section 5, Step 1 and Step 6] The notation switches between z and xi for the underlying random variable in the proof of Theorem 1.3; this should be made uniform.
  4. [Section 3.3] The displayed lower bound 'rho >= C_{1.3}^{-1} 2^{-n^0.04/4}' does not match the hypotheses of Theorem 1.3 as used with s = n^0.9, k = n^0.1; the threshold should be compared with max{e^{-s/k}, s^{-k/4}} and the displayed expression should be corrected.
  5. [Section 3.3, Proposition 3.15] The displayed application of Theorem 1.3 appears to omit the factor s in the denominator of the first term (5np^2/s)^s; this is likely a typesetting issue but should be fixed.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: Theorem 1.1 is proved from the counting theorem Theorem 1.3, which is proved in this paper rather than assumed.

full rationale

The derivation chain is self-contained in the relevant sense. Theorem 1.1 is reduced to Propositions 4.7 and 4.8, and the rich-vector step is reduced to Proposition 4.16, which counts Gaussian integer approximants. That counting bound is supplied by Theorem 1.3, and Theorem 1.3 is proved in Section 5 without invoking Theorem 1.1 or its conclusion. The proof of Theorem 1.3 uses Lemma 5.3 from the author's earlier joint work [7], but Lemma 5.3 is stated and proved inline, and Theorem 5.4, which is the other imported combinatorial input, is proved completely in Appendix A. Thus the load-bearing prior material is reproduced in the paper rather than imported as an unverified black box. The self-citations to [7], [10], and [11] are contextual or concern auxiliary lemmas; none assumes the target estimate. The parameter-mismatch issue raised by the skeptic, namely the application of Theorem 1.3 with p = 2^{n^{0.04}} although the statement requires p ≤ 2n/s = 2n^{0.1}, is a real correctness/hypothesis concern, but it is not circularity: using a theorem outside its stated range does not make the theorem's conclusion an input to itself. No fitted quantity is renamed as a prediction, and no uniqueness or ansatz is imported from a self-citation to force the result.

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

The central claim rests on standard additive-combinatorics facts (Cauchy-Davenport over F_p^2), a permutation concentration inequality from [23], a one-vector invertibility estimate from [37], and the Rademacher counting lemma from [7] by the same authors. No new physical or mathematical entities are postulated, and no parameters are fitted to data. The arbitrary exponents in the theorem are proof parameters, not free parameters.

assumptions (4)
  • standard math Cauchy-Davenport theorem for F_p^2: |A+B| ≥ min{p^2, |A|+|B|-p} for nonempty A,B.
    Used in Section 5, Step 4, to lower-bound the growth of tP'_m(I); the citation is missing ('[?]'), though the theorem is standard.
  • domain assumption Concentration of linear forms of random permutations (Lemma 4.2, from [23]).
    Used to prove Proposition 4.1, the ℓ∞-perturbation anti-concentration estimate needed to handle non-subgaussian noise in the main proof.
  • domain assumption Invertibility along a single fixed vector (Lemma 2.4, from [37]).
    Used in Lemma 4.12 to control compressible vectors; standard anti-concentration plus tensorization.
  • domain assumption Counting lemma for Rademacher variables (Theorem 1.7 in [7]).
    Theorem 5.4 is a slight modification of this prior result by the same authors; it is the basis for the counting bound in Theorem 1.3.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Quantitative invertibility of random matrices: a combinatorial perspective." pith.science (2026). https://pith.science/paper/B4JNFI6W

@misc{pith2026190811255,
  author       = {Pith},
  title        = {Pith review of: Quantitative invertibility of random matrices: a combinatorial perspective},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/B4JNFI6W}},
  note         = {Machine review of arXiv:1908.11255}
}
abstract

We study the lower tail behavior of the least singular value of an $n\times n$ random matrix $M_n := M+N_n$, where $M$ is a fixed complex matrix with operator norm at most $\exp(n^{c})$ and $N_n$ is a random matrix, each of whose entries is an independent copy of a complex random variable with mean $0$ and variance $1$. Motivated by applications, our focus is on obtaining bounds which hold with extremely high probability, rather than on the least singular value of a typical such matrix. This setting has previously been considered in a series of influential works by Tao and Vu, most notably in connection with the strong circular law, and the smoothed analysis of the condition number, and our results improve upon theirs in two ways: (i) We are able to handle $\|M\| = O(\exp(n^{c}))$, whereas the results of Tao and Vu are applicable only for $M = O(\text{poly(n)})$. (ii) Even for $M = O(\text{poly(n)})$, we are able to extract more refined information -- for instance, our results show that for such $M$, the probability that $M_n$ is singular is $O(\exp(-n^{c}))$, whereas even in the case when $\xi$ is a Bernoulli random variable, the results of Tao and Vu only give a bound of the form $O_{C}(n^{-C})$ for any constant $C>0$. As opposed to all previous works obtaining such bounds with error rate better than $n^{-1}$, our proof makes no use either of the inverse Littlewood--Offord theorems, or of any sophisticated net constructions. Instead, we show how to reduce the problem from the (complex) sphere to (Gaussian) integer vectors, where it is solved directly by utilizing and extending a combinatorial approach to the singularity problem for random discrete matrices, recently developed by Ferber, Luh, Samotij, and the author.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

44 extracted references · 42 canonical work pages

  1. [7]

    On the counting problem in inverse Littlewood--Offord theory

    A. Ferber, V. Jain, K. Luh, and W. Samotij. On the counting problem in inverse Littlewood– Offord theory. arXiv:1904.10425, 2019

    work page Pith review arXiv 1904

  2. [1]

    Bourgain, V

    J. Bourgain, V. H. Vu, and P. M. Wood. On the singularity pro bability of discrete random matrices. Journal of Functional Analysis , 258(2):559–603, 2010

    work page 2010

  3. [2]

    A. Edelman. Eigenvalues and condition numbers of random matrices. SIAM Journal on Matrix Analysis and Applications , 9(4):543–560, 1988

    work page 1988

  4. [3]

    P. Erdős. On a lemma of Littlewood and Offord. Bulletin of the American Mathematical Society, 51(12):898–902, 1945. 33

    work page 1945

  5. [4]

    Erdős and L

    P. Erdős and L. Moser. Elementary Problems and Solutions : Solutions: E736. Amer. Math. Monthly, 54(4):229–230, 1947

    work page 1947

  6. [5]

    C. Esseen. On the Kolmogorov-Rogozin inequality for the concentration function. Probability Theory and Related Fields , 5(3):210–216, 1966

    work page 1966

  7. [6]

    Singularity of random symmetric matrices -- a combinatorial approach to improved bounds

    A. Ferber and V. Jain. Singularity of random symmetric ma trices–a combinatorial approach to improved bounds. arXiv:1809.04718

    work page Pith review arXiv

  8. [8]

    Götze, A

    F. Götze, A. Tikhomirov, et al. The circular law for rando m matrices. The Annals of Probability, 38(4):1444–1491, 2010

    work page 2010

Show all 44 references
  1. [9]

    G. Halász. Estimates for the concentration function of c ombinatorial number theory and prob- ability. Periodica Mathematica Hungarica, 8(3-4):197–211, 1977

    1977

  2. [10]

    V. Jain. Approximate Spielman-Teng theorems for the le ast singular value of random combi- natorial matrices. arXiv:1904.10592, 2019

    1904 arXiv

  3. [11]

    V. Jain. The strong circular law: a combinatorial view. arXiv:1904.11108, 2019

    1904 arXiv

  4. [12]

    J. Kahn, J. Komlós, and E. Szemerédi. On the probability that a random ±1-matrix is singular. Journal of the American Mathematical Society , 8(1):223–240, 1995

    1995

  5. [13]

    G. Katona. On a conjecture of Erdős and a stronger form of Sperner’s theorem. Studia Sci. Math. Hungar , 1:59–63, 1966

    1966

  6. [14]

    D. J. Kleitman. On a combinatorial conjecture of Erdős. Journal of Combinatorial Theory , 1(2):209–214, 1966

    1966

  7. [15]

    J. Komlós. On determinant of (0, 1) matrices. Studia Science Mathematics Hungarica , 2:7–21, 1967

    1967

  8. [16]

    J. E. Littlewood and A. C. Offord. On the number of real roo ts of a random algebraic equation. III. Rec. Math. [Mat. Sbornik] N.S. , 12(54):277–286, 1943

    1943

  9. [17]

    A. E. Litvak, A. Pajor, M. Rudelson, and N. Tomczak-Jaeg ermann. Smallest singular value of random matrices and geometry of random polytopes. Advances in Mathematics , 195(2):491– 523, 2005

    2005

  10. [18]

    G. V. Livshyts, K. Tikhomirov, and R. Vershynin. The sma llest singular value of inhomogeneous square random matrices. arXiv preprint arXiv:1909.04219 , 2019

    1909 arXiv

  11. [19]

    K. Luh. Complex random matrices have no real eigenvalue s. Random Matrices: Theory and Applications, 7(01):1750014, 2018

    2018

  12. [20]

    V. D. Milman and G. Schechtman. Asymptotic theory of finite dimensional normed spaces: Isoperimetric inequalities in riemannian manifolds , volume 1200. Springer, 2009

    2009

  13. [21]

    H. H. Nguyen and V. H. Vu. Optimal inverse Littlewood–Off ord theorems. Advances in Mathematics, 226(6):5298–5319, 2011. 34

    2011

  14. [22]

    H. H. Nguyen and V. H. Vu. Small ball probability, invers e theorems, and applications. In Erdős Centennial , pages 409–463. Springer, 2013

    2013

  15. [23]

    Rebrova and K

    E. Rebrova and K. Tikhomirov. Coverings of random ellip soids, and invertibility of matrices with iid heavy-tailed entries. Israel Journal of Mathematics , 227(2):507–544, 2018

    2018

  16. [24]

    Rudelson

    M. Rudelson. Invertibility of random matrices: norm of the inverse. Annals of Mathematics , pages 575–600, 2008

    2008

  17. [25]

    Rudelson and R

    M. Rudelson and R. Vershynin. The Littlewood–Offord pro blem and invertibility of random matrices. Advances in Mathematics , 218(2):600–633, 2008

    2008

  18. [26]

    Rudelson and R

    M. Rudelson and R. Vershynin. No-gaps delocalization f or general random matrices. Geometric and Functional Analysis , 26(6):1716–1776, 2016

    2016

  19. [27]

    Sankar, D

    A. Sankar, D. A. Spielman, and S.-H. Teng. Smoothed anal ysis of the condition numbers and growth factors of matrices. SIAM Journal on Matrix Analysis and Applications , 28(2):446–476, 2006

    2006

  20. [28]

    Sárkőzy and E

    A. Sárkőzy and E. Szemerédi. Über ein Problem von Erdős u nd Moser. Acta Arith., 11:205–208, 1965

    1965

  21. [29]

    D. A. Spielman and S.-H. Teng. Smoothed analysis: an att empt to explain the behavior of algorithms in practice

  22. [30]

    D. A. Spielman and S.-H. Teng. Smoothed analysis of algo rithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM (JACM) , 51(3):385–463, 2004

    2004

  23. [31]

    Tao and V

    T. Tao and V. H. Vu. The condition number of a randomly per turbed matrix. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing , pages 248–255

  24. [32]

    Tao and V

    T. Tao and V. H. Vu. Additive combinatorics, volume 105. Cambridge University Press, 2006

    2006

  25. [33]

    Tao and V

    T. Tao and V. H. Vu. On the singularity probability of ran dom Bernoulli matrices. Journal of the American Mathematical Society , 20(3):603–628, 2007

    2007

  26. [34]

    Tao and V

    T. Tao and V. H. Vu. Random matrices: the circular law. Communications in Contemporary Mathematics, 10(02):261–307, 2008

    2008

  27. [35]

    Tao and V

    T. Tao and V. H. Vu. Inverse Littlewood-Offord theorems a nd the condition number of random discrete matrices. Annals of Mathematics , pages 595–632, 2009

    2009

  28. [36]

    Tao and V

    T. Tao and V. H. Vu. A sharp inverse Littlewood-Offord the orem. Random Structures Algo- rithms, 37(4):525–539, 2010

    2010

  29. [37]

    Tao and V

    T. Tao and V. H. Vu. Smooth analysis of the condition numb er and the least singular value. Mathematics of computation , 79(272):2333–2352, 2010

    2010

  30. [38]

    T. Tao, V. H. Vu, and M. Krishnapur. Random matrices: Uni versality of ESDs and the circular law. The Annals of Probability , 38(5):2023–2065, 2010

    2023

  31. [39]

    Tikhomirov

    K. Tikhomirov. Singularity of random Bernoulli matrice s. arXiv preprint arXiv:1812.09016 , 2018

    2018 arXiv

  32. [40]

    Vershynin

    R. Vershynin. Introduction to the non-asymptotic anal ysis of random matrices. arXiv preprint arXiv:1011.3027, 2010. 35 A Proof of Theorem 5.4 In this section, we prove Theorem 5.4 using an elementary double counting argument appearing in [ 7]. Proof. Let Z be the set of all t...

    2010 arXiv

  33. [41]

    I ⊆ [n] and |I| = s,

  34. [42]

    , in) ∈ [n]n−s is a permutation of [n] \ I,

    (is+1, . . . , in) ∈ [n]n−s is a permutation of [n] \ I,

  35. [43]

    , ℓj,2k) is a sequence of 2k elements of [n], and

    each Fj := (ℓj,1, . . . , ℓj,2k) is a sequence of 2k elements of [n], and

  36. [44]

    ℓj,2k = ij and b

    ǫj ∈ {±1}2k for each j, that satisfy the following conditions for each j: a. ℓj,2k = ij and b. (ℓj,1, . . . , ℓj,2k−1) ∈ ( I ∪ {is+1, . . . , ij−1} )2k−1. Claim A.1. The number of triples in Z is at most (s/n)2k−1 · ( 2n−sn!/s! )2k. Proof. One can construct any such triple as ...

Pith tools

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