OctoInformBeta

OpenAI preprint, September 2026 · §2. The construction and the rank obstruction

Lemma 2.4: An integer matrix with rows of squared norm at most r≥1r \ge 1 has real rank at most twice its rank modulo every prime q>rq > r

Short rows keep half the rank modulo a large prime.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Reduce the entries of an integer matrix modulo a prime qq and its rank can fall: the matrix with rows (1,1)(1,1) and (1,−1)(1,-1) has rank 22 over the reals, while modulo 22 its two rows coincide and its rank is 11. The question is how far the rank can fall when every row is short, in the sense that qq exceeds the sum of the squares of its entries.

Rows, Ranks and Reduction

Let II and JJ be finite sets. An integer matrix MM indexed by I×JI \times J is a family of integers MijM_{ij}, one for each i∈Ii \in I and j∈Jj \in J, with rows indexed by II and columns by JJ; it is square when I=JI = J, and an n×nn \times n matrix when I=J={1,…,n}I = J = \{1, \dots, n\}. Real matrices are indexed in the same way.

For a real number rr, a real or integer matrix MM indexed by I×JI \times J has rows of squared norm at most rr when ∑j∈JMij2≤rfor every i∈I.\sum_{j \in J} M_{ij}^2 \le r \quad \text{for every } i \in I.(1)

For a prime qq, the reduction of an integer matrix MM modulo qq is the matrix M‾\bar M over the field 𝔽q\mathbb{F}_q, indexed by I×JI \times J, whose entry at (i,j)(i,j) is the residue class of MijM_{ij} modulo qq. The real rank rank⁡ℝM\operatorname{rank}_{\mathbb{R}} M is the rank of MM as a matrix over ℝ\mathbb{R}, and rank⁡𝔽qM‾\operatorname{rank}_{\mathbb{F}_q} \bar M is the rank of M‾\bar M over 𝔽q\mathbb{F}_q. A square matrix is nonsingular when its determinant is not zero.

The Claim

Theorem 1. (a) Let MM be an integer matrix indexed by I×JI \times J, for finite sets II and JJ, whose rows have squared norm at most a real number r≥1r \ge 1, and let q>rq > r be a prime. Then rank⁡ℝM≤2rank⁡𝔽qM‾.\operatorname{rank}_{\mathbb{R}} M \le 2 \operatorname{rank}_{\mathbb{F}_q} \bar M.(2)✦

(b) Let AA be a nonsingular integer n×nn \times n matrix whose rows have squared norm at most a real number r≥1r \ge 1, and let q>rq > r be a prime. Then n≤2rank⁡𝔽qA‾.n \le 2 \operatorname{rank}_{\mathbb{F}_q} \bar A.(3)✦

(c) (Hadamard’s inequality.) Let AA be a real n×nn \times n matrix whose rows have squared norm at most a real number rr. Then (det⁡A)2≤rn.(\det A)^2 \le r^n.(4)✦

(d) Let AA be a square integer matrix indexed by I×II \times I, for a finite set II, and let qq be a prime. Then q|I|−rank⁡𝔽qA‾dividesdet⁡A.q^{\,|I| - \operatorname{rank}_{\mathbb{F}_q} \bar A} \ \text{divides} \ \det A.(5)✦

In the paper, the result reads: for an integer matrix MM whose rows have Euclidean norm at most r\sqrt{r}, where r≥1r \ge 1, and for every prime q>rq > r, rank⁡𝔽qM‾≥12rank⁡ℝM\operatorname{rank}_{\mathbb{F}_q} \bar M \ge \tfrac{1}{2} \operatorname{rank}_{\mathbb{R}} M.

What Is Checked

The claim is stated over matrices indexed by finite sets, integer in (2), (3) and (5) and real in (4): the squared norms of their rows as in (1), the real rank, the rank over 𝔽q\mathbb{F}_q of the reduction modulo a prime qq, and the determinant of a square matrix.