A power improvement in the Heilbronn triangle lower bound

Introduction

For three points $p,q,r \in\mathbb{R}^2$, write

If $P \subset[0,1]^2$ is finite and $\lvert P\rvert\ge3$, define

The minimum is over all unordered triples of distinct points. In particular, a collinear triple makes $\Delta(P)=0$. The maximum defining $\Delta(n)$ exists: the minimum area is continuous on the compact space of ordered $n$-tuples, it is positive for suitable points on a parabola, and a tuple with a repeated point has minimum area zero.

The original Heilbronn conjecture asked whether $\Delta(n)=O(n^{-2})$; see Roth [12], p. 198. Two elementary constructions attain this scale. Erdős’s finite-field parabola, recorded in Roth [12], Appendix, gives a grid configuration whose triangle determinants are nonzero integers before scaling. Random sampling followed by deleting one point from each small triangle also gives $\Delta(n)\gg n^{-2}$. Komlós, Pintz and Szemerédi improved this to $\Delta(n)\gg(\log n)/n^2$, disproving the original conjecture [10]. Their argument represents the small-area triples in a random point set as edges of a hypergraph, removes short cycles, and uses a stronger independence bound to select a large subset containing none of those triples [10], Section 2.

The almost $n^{-2}$ formulation, discussed in Zakharov’s survey [18], Section 3, asks whether, for every $\varepsilon>0$, there are constants $C_\varepsilon$ and $n_0(\varepsilon)$ such that

We disprove this formulation by a power improvement in the lower bound.

Theorem 1.1. There are absolute constants $\eta$, $c_1>0$ and an integer $n_0\ge3$ such that

In particular, $\Delta(n)\ge n^{-2+\eta/2}$ for every sufficiently large $n$. The ratio of the theorem’s lower bound to $n^{-2+\eta/2}$ is $c_1n^{\eta/2}\to\infty$, which contradicts (1.1) at $\varepsilon=\eta/2$. Section 8 gives an explicit, though extremely small, admissible exponent.

On the upper-bound side, Roth [12] proved the first $o(n^{-1})$ estimate by a density-increment argument, followed by refinements of Schmidt [16] and Roth [13, 14]. Komlós, Pintz and Szemerédi [9] refined Roth’s analytic method to obtain $\Delta(n)\ll_\varepsilon n^{-8/7+\varepsilon}$. Cohen, Pohoata and Zakharov developed new incidence-geometric approaches, first obtaining $\Delta(n)\le n^{-8/7-1/2000}$ for sufficiently large $n$ [4], Theorem 1.1, and subsequently proving $\Delta(n)\ll_\varepsilon n^{-7/6+\varepsilon}$ for every $\varepsilon>0$ [5], Theorem 1.8.

Earlier preprints claim stronger power lower bounds than ours, with unresolved issues in the following versions. Ellmann’s version 12 acknowledges an unproved local uniformity assumption and describes the argument as heuristic [6], p. 3; the deletion estimate uses this assumption [6], Theorem 4, pp. 5–6. In Agama’s version 13, Theorem 4.1 [1], pp. 12–13, counting the center with the boundary points introduces a collinear triple consisting of the two endpoints of a diameter and their midpoint. Omitting the center leaves the every-triple estimate unproved, since the argument estimates triangles formed by the center and adjacent boundary points. These objections concern the cited arguments, not the impossibility of their asserted bounds.

The two congruence conditions

The proof works first with integer columns $u=(u_1,u_2,u_3)^{\mathsf T}$ in a box of the form

Such a column represents the unit-square point $\pi(u)=(u_1/u_3,u_2/u_3)$. Three columns forming a matrix $A$ give a triangle of area

We therefore seek many columns for which proportional pairs and triples with small absolute determinant are sufficiently rare to delete.

The first congruence condition separates most triples before they are lifted to integers. Give each column an independent uniform label $\xi\in\mathbb{F}_{r^d}$, where $d$ is fixed and odd and the prime $r$ grows. The columns $(1,\xi,\xi^2)^{\mathsf T}$ have nonzero determinant whenever their labels are distinct. This is the finite-field parabola underlying Erdős’s construction recorded in Roth [12]. Taking the field norm to $\mathbb{F}_r$ produces an alternating polynomial in three groups of coordinates. We express that polynomial as a sum of monomial determinants and encode it in one designated coefficient of a determinant whose entries are base-$B$ expansions. Large-base control of carries has classical precedents in the progression-free constructions of Salem and Spencer [15] and Behrend [3]; here it isolates a determinant coefficient. Modulo $h=B^k$, with $k$ fixed, distinct labels then preclude a small determinant. Independent choices of digits with the prescribed residues leave enough randomness even when labels coincide.

A common random matrix of determinant one mixes the three rows modulo $h$ without changing their determinant. Conditional on the digit columns, the resulting matrix is uniform on a special-linear orbit. The rows of every integral lift lie in a lattice whose index, together with the orbit size, can be read from a diagonal form. An anisotropic lattice count controls lifts of any fixed nonzero determinant, while a conditional moment bound handles singular digit matrices and repeated labels.

The fixed nonzero-determinant count does not cover determinant zero, where all three rows can lie in one integral plane. We control this case with a second congruence condition. At an independent prime $q$, choose residues from a small portion of an affine quadratic surface with no three points on a line. A carefully restricted random translation excludes short integer relations; a random invertible linear map permits uniform counting. The Chinese remainder theorem combines the two congruence conditions, and uniform lifting supplies integer columns in the box.

For a singular lifted matrix with pairwise distinct projected columns, a primitive integer null vector determines a rank-two row lattice. We sum over those vectors, treating equal residue columns and low rank modulo $q$ separately. This supplies the missing count for collinear projected triples.

The exceptional triples require repeated labels, whose probability provides the saving used in an elementary deletion argument. Thus the improvement comes from the arithmetic distribution of sampled points. Formula (1.2) then transfers the determinant bound to every triangle of the retained point set.

Organization and conventions

Section 2 proves the lattice estimates. Section 3 constructs the norm polynomial and digit distribution, and Section 4 estimates its matrix orbits. Section 5 constructs the auxiliary residues. Sections 6 and 7 count small determinants, including zero. Section 8 completes the deletion and scaling argument and passes to every sufficiently large cardinality. Appendix A gives the elementary prime-interval proof used in the parameter choices and interpolation.

Lengths are Euclidean. A primitive integer vector has coordinates with greatest common divisor one. The covolume of a lattice is measured in its real span. The notation $F \ll G$ means $\lvert F\rvert\le CG$; constants may depend on the fixed construction parameters, but never on the growing prime or on the sampled labels and columns. All logarithms are natural.

Lattice counts with a prescribed determinant

We prove a uniform bound for integer matrices whose rows belong to a fixed lattice and whose determinant is a prescribed nonzero integer. The lattice may have very different scales in different directions, so the proof keeps track of three separate column bounds. We also record the plane counts needed when the determinant is zero.

All lengths in this section are Euclidean. The determinant of a lattice means its covolume in its real span. For a lattice $L$ of positive rank $s$, choose $v_1,\ldots,v_s$ successively, with $v_i$ a shortest lattice vector outside $\operatorname{span}_{\mathbb{R}}(v_1,\ldots,v_{i-1})$, and put $\lambda_i=\lvert v_i\rvert$. In particular, $0<\lambda_1\le\cdots\le\lambda_s$. The notation $A\ll B$ means $A\le CB$ for an absolute constant $C$, unless dependence is indicated.

The classical geometry-of-numbers antecedent is Minkowski’s second theorem on successive minima; see Henk [8]. Only the weaker fixed-dimensional Euclidean product bound below is needed here, and we include its proof.

Lemma 2.1 (Successive lengths). For a lattice $L$ of positive rank $s$ and the lengths just defined,

Consequently, the lattice generated by $v_1,\ldots,v_s$ has index at most $s^{s/2}$ in $L$.

Proof. The determinant of the lattice generated by the $v_i$ is an integer multiple of $\det L$ and is at most $\prod_i\lambda_i$. For the reverse bound, choose orthonormal coordinates whose first $j$ directions span $v_1,\ldots,v_j$ for each $j$. Let

If a nonzero lattice vector in $Q$ has last nonzero coordinate $j$, it lies outside the preceding span and has length strictly less than $\lambda_j$, a contradiction. The translates of $Q/2$ by $L$ are therefore disjoint. Integrating their indicator functions over a fundamental domain of $L$ gives $\operatorname{vol}(Q/2)\le\det L$. Since $\operatorname{vol}(Q/2)=s^{-s/2}\prod_i\lambda_i$, the result follows. □

Lemma 2.2 (Points in a plane lattice). Let $L$ be a rank-two Euclidean lattice with successive lengths $\lambda_1\le\lambda_2$. If $R\ge\lambda_2$, any translate of $L$ has at most $CR^2/\det L$ points in any ball of radius $R$. If $R<\lambda_2$, the points of $L$ in the ball of radius $R$ centered at zero lie in a line and number at most $1+2R/\lambda_1$.

Proof. For the first assertion let $L_0=\mathbb{Z}v_1+\mathbb{Z}v_2$. A half-open fundamental parallelogram for $L_0$ has diameter at most $\lambda_1+\lambda_2\le2R$. For each coset of $L_0$, attach such a parallelogram to every point in the ball. The parallelograms are disjoint and lie in a disk of radius at most $3R$ in the affine span. Thus each coset contributes at most $9\pi R^2/\det L_0$ points. Summing over $[L:L_0]$ cosets proves the first assertion. For the second, every lattice vector outside $\mathbb{R}v_1$ has length at least $\lambda_2$. The lattice on $\mathbb{R}v_1$ is $\mathbb{Z}v_1$, since a shorter generator would contradict the choice of $v_1$. Counting its multiples proves the bound. □

Lemma 2.3 (Covolumes of integral planes). Let $y \in\mathbb{Z}^3$ be primitive, meaning that its coordinates have greatest common divisor one. Then $L_y = \mathbb{Z}^3 \cap y^\perp$ has determinant $|y|$. More generally, if $\Lambda\subseteq\mathbb{Z}^3$ is a full-rank lattice of index $I$ and $y \cdot\Lambda= g\mathbb{Z}$ with $g > 0$, then

Proof. Choose $u \in\Lambda$ with $y \cdot u = g$. The map $v \mapsto y \cdot v/g$ maps $\Lambda$ onto $\mathbb{Z}$, has kernel $\Lambda\cap y^\perp$, and splits by $1 \mapsto u$. Hence a basis of the kernel together with $u$ is a basis of $\Lambda$. The height of $u$ above $y^\perp$ is $g/|y|$, which proves the formula. For $\Lambda= \mathbb{Z}^3$, primitivity gives $g = 1$.

We next count matrices with unequal column bounds. The difficult case occurs when the third-column radius reaches only one direction of its integral plane; we count those planes through their shortest vectors.

Lemma 2.4 (Unequal column bounds). Let $R_1 \ge R_2 \ge R_3 \ge1$ and let $t \in\mathbb{Z} \setminus\{0\}$. The number of triples $u_1, u_2, u_3 \in\mathbb{Z}^3$ satisfying $|u_j| \le R_j$ and $\det(u_1,u_2,u_3) = t$ is at most

The constant is independent of $t$ and of the three radii.

Proof. The columns $u_2,u_3$ are independent. Choose a primitive normal $y$ to their plane, fixing its sign by requiring its first nonzero coordinate to be positive. Then $u_2 \times u_3 = ay$ for some nonzero integer $a$, so $|y| \le R_2R_3$. If $\mu_1,\mu_2$ are the successive lengths of $L_y$, the columns imply $\mu_1 \le R_3$ and $\mu_2 \le R_2$.

For fixed $u_2,u_3$, the determinant equation is $u_1 \cdot y = t/a$. Its integral solutions are either absent or form a translate of $L_y$. By Lemmas 2.2 and 2.3, at most $CR_1^2/|y|$ satisfy the first-column bound; the required hypothesis is $\mu_2 \le R_2 \le R_1$. For a fixed normal $y$, there are likewise at most $CR_2^2/|y|$ choices for $u_2$.

First suppose $\mu_2 \le R_3$. There are at most $CR_3^2/|y|$ choices for $u_3$. The resulting bound, summed over normals, is

The last estimate follows by splitting the integer vectors into dyadic shells; a shell of radius $Y \ge1$ has $O(Y^3)$ vectors.

It remains to treat $\mu_2 > R_3$. Group the normals by powers of two $U,Z \ge1$ with

Lemma 2.1 gives $|y| \asymp UZ$. There are at most $CU^4Z^2$ normals in such a group. Indeed, choose a shortest nonzero vector $z \in L_y$. It is primitive in $\mathbb{Z}^3$, because division by a common divisor would produce a shorter vector in $L_y$. Its length is in $[U,2U)$, giving $O(U^3)$ choices. For each such $z$, the possible normals lie in $L_z$ and have length less than $4UZ$. If $\nu_1,\nu_2$ are the successive lengths of $L_z$, integrality gives $\nu_1 \ge1$, and the preceding lemmas give

Consequently Lemma 2.2, applied at radius $4UZ$, bounds their number by $C(UZ)^2/|z| \le CUZ^2$. This proves the claimed normal count.

For each of these normals, all eligible third columns lie on the line of a shortest vector. Lemma 2.2 gives at most $1+2R_3/\mu_1 \ll R_3/U$ choices, since $U \le\mu_1 \le R_3$. Thus the contribution of one dyadic group is at most

There are $O(\log(2R_3)\log(2R_2))$ groups, since $1 \le U \le R_3$ and $1 \le Z \le R_2$. Combining both cases proves the assertion.

Proposition 2.5 (A fixed nonzero determinant). Let $\Lambda\subseteq\mathbb{Z}^3$ have index $I$, let $X \ge2$, and suppose its third successive length satisfies $\lambda_3 \le X$. For every $t \in\mathbb{Z} \setminus\{0\}$, the number of $3$ by $3$ matrices with rows in $\Lambda$, row lengths at most $X$, and determinant $t$ is at most

The constant is absolute.

Proof. Let $V$ be the matrix whose rows are the successive shortest vectors $v_1,v_2,v_3$, and let $\Lambda_0$ be their integer span. By Lemma 2.1,

Since the finite group $\Lambda/\Lambda_0$ has order $m$, each $u\in\Lambda$ has coordinates in $m^{-1}\mathbb{Z}$ relative to this basis. If $u=\sum_j\alpha_jv_j$ and $|u|\le X$, Cramer’s rule gives

Thus the map $A\mapsto Q=mAV^{-1}$ is injective and takes the matrices under consideration to integral matrices. Their common determinant is $m^3t/\det V\ne0$. If this number is not an integer, there are no such matrices; otherwise Lemma 2.4 applies.

The $j$th column of $Q$ has length at most $R_j=C_0X/\lambda_j$, where $C_0$ is an absolute constant chosen sufficiently large. These radii satisfy $R_1\ge R_2\ge R_3\ge1$. Moreover, integrality of $\Lambda$ gives $\lambda_j\ge1$, and Lemma 2.1 gives

The bound in Lemma 2.4 is therefore the claimed one.

A determinant obstruction from field norms

We construct random columns modulo a prime power, each carrying a label in a finite field. Three distinct labels will force the determinant residue to have no small integer representative. The construction first expresses a field norm as a sum of determinants, then places these summands at one specified coefficient in a base expansion.

The norm polynomial

Fix

Let $r$ be an odd prime. We recall the elementary finite-field facts needed here; see [11] for background. In a splitting field over $\mathbb{F}_r$, the roots of $X^{r^d}-X$ form a field: the Frobenius identity shows closure under addition, subtraction and multiplication, and nonzero roots are closed under inversion. The derivative is $-1$, so there are exactly $r^d$ distinct roots. This field, denoted $K=\mathbb{F}_{r^d}$, consequently has dimension $d$ over $\mathbb{F}_r$. Its automorphism $t\mapsto t^r$ has $d$th power equal to the identity, and its fixed elements are exactly the $r$ roots of $X^r-X$, namely $\mathbb{F}_r$. For $t\in K$, the product $\prod_{j=0}^{d-1}t^{r^j}$ is therefore fixed by Frobenius and belongs to $\mathbb{F}_r$; it is nonzero if $t\ne0$. Choose an $\mathbb{F}_r$-basis $\beta_1,\ldots,\beta_d$ of $K$. For a group $X=(X_{i\nu})_{1\le i\le3,\,1\le\nu\le d}$ of $3d$ variables, define

For three disjoint variable groups $X^{(1)},X^{(2)},X^{(3)}$, put

Let $\sigma$ act on this polynomial ring by applying $c\mapsto c^r$ to coefficients in $K$ and fixing every variable. Define

The action of $\sigma$ permutes the factors, so $\mathcal{N}$ has coefficients in $\mathbb{F}_r$. It is homogeneous of degree $d$ in each group. At arguments in $\mathbb{F}_r^{3d}$, it evaluates to the field norm of the corresponding determinant:

Indeed, coefficient conjugation commutes with evaluation at such arguments. Transposing two variable groups changes the sign of each factor in (2). Since $d$ is odd, $\mathcal{N}$ is alternating.

Lemma 3.1. There exist homogeneous degree-$d$ polynomials $f_{ia}\in\mathbb{F}_r[X]$ (allowing the zero polynomial), for $1\le i\le3$ and $0\le a<T$, such that

For each $a$, the three polynomials are obtained from three distinct degree-$d$ monomials by multiplying the first by a scalar that may be zero.

Proof. List the degree-$d$ monomials in $3d$ variables as $m_1,\ldots,m_M$. Expand $\mathcal{N}$ in products $m_p(X^{(1)})m_q(X^{(2)})m_s(X^{(3)})$. If two of $p,q,s$ coincide, the coefficient equals its negative under the corresponding transposition, and hence is zero because $r$ is odd. For each $p<q<s$, let $c_{pqs}$ be the coefficient of $m_p(X^{(1)})m_q(X^{(2)})m_s(X^{(3)})$. Alternation identifies the other five coefficients with the signs in

Enumerate the $T$ triples $p<q<s$ by $a$, and take

This argument uses no division by $3!$, so it applies also when $r=3$.

For a label $\xi\in K$, set $z(\xi)=(1,\xi,\xi^2)^{\mathsf{T}}$ and let $X(\xi)\in\mathbb{F}_r^{3d}$ be its coordinates in the chosen basis, so that $Z(X(\xi))=z(\xi)$. The Vandermonde determinant gives

whenever the three labels are distinct. Although the basis and the coefficients $f_{ia}$ may depend on $r$, the numbers $d,M,T,k$ in (3.1) do not.

Encoding the polynomial in a base expansion

Two prime choices will keep the construction parameters polynomial in $r$. We use the following sufficiently-large form of Bertrand’s postulate; Appendix A gives its elementary binomial proof, following Erdős [7].

Lemma 3.2. For every sufficiently large integer $n$, there is a prime $p$ with $n<p\le2n$.

Set $L=r^{10}$. For all sufficiently large $r$, apply Lemma 3.2 with $n=100k^2L^3$ to choose a prime $B$ satisfying

For $0\le a<T$, designate positions in rows $1,2,3$, respectively, by

These positions lie in $\{0,\ldots,k-1\}$ and are distinct within each row: they lie respectively in the intervals $[0,T-1]$, $[0,T^2-T]$, and $[1,T^2]$. The only designated positions whose sum is $k-1$ are the matched triples:

To prove the forward implication, rewrite the equation as $a+Ta'=(T+1)a''$. Reduction modulo $T$, together with $0\le a,a''<T$, gives $a=a''$; substitution then gives $a'=a''$. The reverse implication follows from (3.6).

A random column $c=(c_1,c_2,c_3)^{\mathsf{T}}\in R_h^3$ is now defined as follows. First choose $\xi$ uniformly from $K$. For each row $1\le i\le3$ and each position $0\le v<k$, choose an integer digit $c_{iv}\in\{1,\ldots,L\}$. Its required residue modulo $r$ is $f_{1a}(X(\xi))$ when $(i,v)=(1,i_a)$, $f_{2a}(X(\xi))$ when $(i,v)=(2,j_a)$, and $f_{3a}(X(\xi))$ when $(i,v)=(3,\ell_a)$. At every other position its required residue is zero. Conditional on $\xi$, choose all $3k$ digits independently and uniformly subject to these requirements, and set

Every required residue has exactly $L/r=r^9$ possible digits, including the zero residue. In particular a digit prescribed to be zero modulo $r$ is still a positive integer. Since $L<B$, the lowest digit is a unit modulo $B$; thus every entry of $c$ is a unit in $R_h$. Different columns use independent labels and fresh independent digits, even when their labels coincide.

Lemma 3.3 (Determinant obstruction). Let $C$ be a matrix of three columns constructed by (3.8), with labels $\xi_1,\xi_2,\xi_3$. If these labels are distinct, then the residue $\det C\in R_h$ has no integer representative in $[-\tau,\tau]$.

Proof. Write $c_{iv}^{(j)}$ for the digit at row $i$, position $v$, in column $j$. Form the integer polynomial

For a fixed exponent $u$ and each of the six determinant permutations, choosing the first two digit positions determines the third. Therefore

Alternatively expanding by rows, $\gamma_{k-1}$ is the sum of determinants of digit rows at positions whose sum is $k-1$. Modulo $r$, all terms with an undesignated position vanish. By (3.7), the surviving terms are exactly those in (2), evaluated at the three label vectors. Consequently

which is nonzero by (3). In particular $\lvert\gamma_{k-1}\rvert\ge1$ as an integer.

The integer

represents $\det C$ modulo $h$, because all omitted terms in $F(B)$ are divisible by $B^k$. Since $B-1\ge100k^2L^3$, the coefficient bound gives

It follows that

By (6), every other representative $S_C+mh$, $m\in\mathbb{Z}\setminus\{0\}$, has absolute value greater than $h/2>\tau$. This proves the assertion.

In particular, if $G\in\operatorname{SL}_3(R_h)$ and an integer matrix $A$ satisfies $A\bmod h=GC$ and $\lvert\det A\rvert\le\tau$, then at least two labels of $C$ coincide: multiplication by $G$ preserves its determinant residue. For three independently sampled labels, the probability of such a coincidence is at most $3r^{-d}$ by the union bound.

Residue orbits and a conditional divisor estimate

We now describe the lattice of possible rows after a change of coordinates modulo a prime power. The size of the corresponding special-linear orbit will control the probability of a prescribed lifted matrix. Two divisors measure the singularity of the residue matrix; the smaller one has bounded expectation even after all three labels have been fixed.

Throughout this section, let $B$ be a prime, let $k \ge1$ be an integer, and put $h = B^k$ and $R_h = \mathbb{Z}/h\mathbb{Z}$. We interpret $B^k$ as zero when it occurs as an entry of a matrix over $R_h$, but as the positive integer $h$ in counting formulas. The row span of a matrix over $R_h$ is the $R_h$-submodule generated by its rows.

The diagonal reduction below is the prime-power-ring form of Smith’s normal form; see Smith [17], Articles 12–16 for the classical integer reduction and determinantal divisors. We include the elementary proof needed here, including singular cases.

Lemma 4.1 (Diagonal form and the row lattice). Let $C \in M_3(R_h)$ have at least one unit entry. There are invertible matrices $P,Q \in\operatorname{GL}_3(R_h)$ and integers $0 \le b \le e \le k$ such that

Set $D = B^b$, $E = B^e$, and $I = DE$, all as positive integers. The subgroup

is a full lattice satisfying

Moreover, $b \ge j$, for $1 \le j \le k$, if and only if every $2 \times2$ minor of $C$ vanishes modulo $B^j$.

Proof. Move a unit entry into the first position, scale it to $1$, and clear the rest of its row and column by invertible operations. In the remaining $2 \times2$ block choose a nonzero entry of least $B$-adic valuation $b$, move it to the first position of that block, and multiply by a unit to make it $B^b$. Every other entry of the block is divisible by $B^b$ in $R_h$, so row and column subtraction clear its row and column. The final entry is still divisible by $B^b$; scaling it by a unit makes it $B^e$ with $b \le e \le k$. If the block is zero, take $b = e = k$. This proves the stated form, including all zero-pivot cases.

Invertible row and column operations preserve the ideal generated by the $2 \times2$ minors: each new minor is a linear combination of old minors, and the inverse operations give the reverse inclusion. For the diagonal matrix this ideal is $B^bR_h$. Its image modulo $B^j$ is zero exactly when $b \ge j$, proving the last assertion and, in particular, showing that $b$ is independent of the diagonalization.

Write $\mathcal{M}$ for the row span of $C$. Left multiplication by $P$ does not change the row span, while multiplication on the right by $Q$ is an automorphism of $R_h^3$. Hence

The reduction map identifies $\mathbb{Z}^3/\Lambda_C$ with $R_h^3/\mathcal{M}$, which proves the index formula. Since $D$ divides $E$, the diagonal row span contains $ER_h^3$. Right multiplication by $Q$ preserves $ER_h^3$, so $\mathcal{M}$ also contains $ER_h^3$. Taking inverse images proves the containment in (4.1). $\square$

The preceding description permits singular matrices: either or both of the last two diagonal entries may be zero. The orbit estimate must retain these cases, because zero determinants are included in the triangle problem.

Lemma 4.2 (A special-linear orbit bound). Under the hypotheses and notation of Lemma 4.1, define

There is an absolute constant $c_0>0$ such that

For a uniformly chosen $G\in\mathrm{SL}_3(R_h)$, the matrix $GC$ is uniform on $\mathcal{O}_C$. Every matrix in this orbit has the same row span and determinant as $C$.

Proof. Let $\mathcal{G}=\mathrm{GL}_3(R_h)$, and let $\mathcal{H}$ be the stabilizer of $C$ under left multiplication. Conjugation by $P$ identifies $\mathcal{H}$ with the stabilizer of $\operatorname{diag}(1,D,E)$ and preserves determinants. An element of this latter stabilizer has first column exactly $(1,0,0)^{\mathsf T}$. Its second column differs from $(0,1,0)^{\mathsf T}$ by three entries annihilated by $D$, and its third column differs from $(0,0,1)^{\mathsf T}$ by three entries annihilated by $E$. The respective annihilators have $D$ and $E$ elements. Discarding the invertibility condition gives

For every unit $u\in R_h^\times$ with $u\equiv1\pmod{h/E}$, the matrix $\operatorname{diag}(1,1,u)$ stabilizes $\operatorname{diag}(1,D,E)$. If $e<k$, there are exactly $E$ such units. If $e=k$, this congruence imposes no restriction, so there are $\varphi(h)=(1-B^{-1})E$ of them. Consequently, in all cases,

Here $\det\mathcal{H}$ denotes the image of the determinant homomorphism on $\mathcal{H}$. The determinant map from $\mathcal{G}$ onto $R_h^\times$ has kernel $\mathrm{SL}_3(R_h)$. Applying the orbit–stabilizer formula in these two groups gives the exact identity

Reduction modulo $B$ shows that

Together with (4.3) and (4.4), this proves (4.2), for example with $c_0=21/64$. Every fiber of the map $\mathcal{G}\to GC$ is a coset of its stabilizer, which proves uniformity. The assertions about row spans and determinants follow directly from invertibility and $\det G=1$.

We next estimate the smaller divisor $D$ for digit columns. Only the independence and number of digit choices matter here; their prescribed residues may be arbitrary functions of the labels.

Lemma 4.3 (Conditional digit estimate). Let $r,L$ be positive integers with $r\ge2$, $r\mid L$, and $L<B$. Let $\mathcal{L}$ be a label set, and for each $\lambda\in\mathcal{L}$, $1\le i\le3$, and $0\le u<k$, prescribe a residue $a_{iu}(\lambda)\in\mathbb{Z}/r\mathbb{Z}$. Fix any three labels $\lambda_1,\lambda_2,\lambda_3$, allowing repetitions. Independently for every $i,j,u$, choose $d_{iju}$ uniformly from

and define $C \in M_3(R_h)$ by

Let $b$ and $D=B^b$ be as in Lemma 4.1, and put $\theta=B(r/L)^4$. Then, for every $1\le j\le k$,

If $\theta<1$, then

Proof. Every prescribed digit set has exactly $L/r$ elements. Since the lowest digit belongs to $\{1,\ldots,L\}$ and $L<B$, every entry of $C$ is a unit in $R_h$.

In addition to the three labels, condition on the complete first column of $C$ and the first entries of its other two columns. If $b\ge j$, Lemma 4.1 implies, for $i,v\in\{2,3\}$,

The right sides are fixed under this conditioning. Each congruence determines the first $j$ base-$B$ digits of its entry, since all chosen digits lie between $0$ and $B-1$. It therefore has probability either zero or $(r/L)^j$. The four entries use disjoint independent digit draws, even if their labels agree. Their joint probability is at most $(r/L)^{4j}$. Averaging over the additional conditioning proves (12), including $j=k$.

Finally, the pointwise identity

and (12) give (13).

For the parameters $L=r^{10}$ and $B\le200k^2L^3$ of the digit construction, we have

Thus, for fixed $k$ and all sufficiently large $r$,

In particular, suppose the labels are independent and uniform in a set of size $r^d$, and let $\mathcal{E}$ be the event that at least two labels coincide. The union bound and conditioning on the labels yield

This is the estimate needed when the digit obstruction restricts a small determinant to triples with repeated labels.

An auxiliary cap and its inclusion probabilities

The determinant obstruction at the main modulus leaves triples with repeated labels. We now impose an independent restriction at a second prime. This restriction excludes short integer relations among three distinct residue columns and gives bounds for the probability of each remaining triple, including triples with equal residue columns.

Retain the main modulus $h \ge2$, and choose a prime $q$ with

Lemma 3.2 supplies such a prime for all sufficiently large $h$. These choices imply $q \ge2000H^2$, and hence

We identify the integers $0,\ldots,w-1$ with their residues in $\mathbb{F}_q$.

The following construction uses an affine part of a classical elliptic quadric, a cap with no three collinear points; see Barlotti [2]. The proof also gives the required intersection with a small box.

Lemma 5.1. Let $q$ be an odd prime and $1 \le w \le q$ an integer. There is a set $S \subset\{0,\ldots,w-1\}^3 \subset\mathbb{F}_q^3$ with $|S| \ge w^3/q$ such that no affine line contains three distinct points of $S$.

Proof. Choose a nonsquare $\nu\in\mathbb{F}_q$ and put

The form $Q$ vanishes only at $(0,0)$. On a line with nonzero direction $(v_1,v_2)$ in its first two coordinates, the equation defining $\Gamma$ is a quadratic equation in the line parameter with nonzero leading coefficient $Q(v_1,v_2)$. Such a line meets $\Gamma$ at most twice. A line with direction $(0,0,v_3)$ meets $\Gamma$ exactly once. Thus $\Gamma$, and every translate of it, has the asserted line property.

For a uniform $b \in\mathbb{F}_q^3$, every point belongs to $b+\Gamma$ with probability $|\Gamma|/q^3=1/q$. Therefore the average of $|(b+\Gamma)\cap\{0,\ldots,w-1\}^3|$ is $w^3/q$. Choose a translate attaining at least this average and take its intersection with the box. □

Fix one such set $S$ for the parameters in (5.1), and write $s=|S|$. In particular,

The set $S$ is fixed before any random choices are made.

For $t\in\mathbb{F}_q$, write $\|t\|_q$ for the least absolute value of an integer representative of $t$. Three distinct cap points already exclude nontrivial relations over $\mathbb{F}_q$ whose coefficients sum to zero. For a shift $a\in\mathbb{F}_q^3$, a relation among three points of $a+S$ with integer coefficients $|x_i|\le H$ and nonzero sum $m=x_1+x_2+x_3$ would force $\|ma_1\|_q\le3Hw$. We exclude this possibility by defining the set of allowed shifts

Choose $a$ uniformly from $A$, and independently choose $G_q$ uniformly from $\operatorname{GL}_3(\mathbb{F}_q)$. Our auxiliary set is

Here and below a triple $u^{(1)},u^{(2)},u^{(3)}$ is affinely independent if $u^{(2)}-u^{(1)}$ and $u^{(3)}-u^{(1)}$ are linearly independent. This allows the three columns to have linear rank two.

Lemma 5.2. Let $H \ge1$ be an integer, let $q \ge2000H^2$ be prime, and put $w = \lfloor q/(1000H^2) \rfloor$. Suppose $S \subset\{0,\ldots,w-1\}^3$ contains no three distinct collinear points. The set $A$ in (16) has at least $q^3/2$ elements. For every $a \in A$ and every invertible $G_q$, the set $V$ in (5.4) has $|S|$ elements, does not contain zero, and contains no three distinct collinear points.

Moreover, let $x = (x_1,x_2,x_3) \in\mathbb{Z}^3 \setminus\{0\}$ satisfy $|x| \le H$, where $|x|$ is the Euclidean norm. For any $u^{(1)},u^{(2)},u^{(3)} \in V$, the relation

is impossible if $x_1+x_2+x_3 \ne0$. If $x_1+x_2+x_3=0$, it is impossible whenever the three columns are affinely independent. Consequently, (17) is impossible for three distinct elements of $V$.

Proof. For each integer $1 \le m \le3H < q$, multiplication by $m$ permutes $\mathbb{F}_q$. Since $3Hw<q/2$, a uniform shift violates the condition for this $m$ with probability $(6Hw+1)/q$. The union bound gives

Thus the required uniform choice of $a$ is defined. Invertible affine maps preserve cardinality and the line property. If $a+v=0$ for some $v \in S$, then $\lVert a_1\rVert_q \le w-1 \le3Hw$, contrary to the condition with $m=1$. Hence $0 \notin V$.

Write $u^{(i)}=G_q(a+v^{(i)})$ with $v^{(i)}\in S$, and let $m=x_1+x_2+x_3$. If $m\ne0$, then $1\le|m|\le3H$. Applying $G_q^{-1}$ to (17) and taking first coordinates gives

The integer on the right, using the representatives $0\le v_1^{(i)}<w$, has absolute value at most $3H(w-1)$. Since $\lVert ma_1\rVert_q=\lVert|m|a_1\rVert_q$, this contradicts (16).

If $m=0$, the coefficients in (17) have sum zero also in $\mathbb{F}_q$. They are not all zero there, since $x\ne0$ and $|x_i|\le H<q$. Such a relation contradicts affine independence: substituting $x_3=-x_1-x_2$ would give a nontrivial linear relation between $u^{(1)}-u^{(3)}$ and $u^{(2)}-u^{(3)}$. Finally, three distinct elements of $V$ are affinely independent by the line property.

The restricted shift excludes short relations. We next show that this restriction costs only a constant in the inclusion probability of an affinely independent triple, and obtain the weaker bounds needed when residue columns coincide.

For an integer $3\times3$ matrix $A$, define

The probability is over $a$ and $G_q$; $S$ remains fixed.

Proposition 5.3. For the distribution in (5.4), with $s=|S|\ge1$, the following bounds hold with absolute constants:

If $W(A)>0$, no column of $A\mathbin{\bmod}q$ is zero, and its columns are either affinely independent or include two equal columns. For an affinely independent triple with $W(A)>0$, there is no nonzero $x\in\mathbb{Z}^3$ with $|x|\le H$ and $Ax=0\pmod q$.

Proof. First replace the allowed shift by an unconditional uniform $a \in\mathbb{F}_q^3$. Under this replacement the map $v \mapsto G_qv + G_qa$ is uniform in the affine group: conditional on $G_q$, its translation $G_qa$ is uniform. Conditioning back on $a \in\mathcal{A}$ increases the probability of any event by at most two, by Lemma [5].

The affine group acts transitively on the ordered affinely independent triples in $\mathbb{F}_q^3$, whose number is

There are $s(s-1)(s-2)$ such triples in $S$. Therefore, for an affinely independent triple of columns,

For the other two bounds, fix any allowed $a$ and put $S_a=a+S$. If two specified target columns are linearly independent, their inverse images under a uniform $G_q$ are uniform among the $(q^3-1)(q^3-q)$ ordered independent pairs. At most $s^2$ of these pairs belong to $S_a^2$. Requiring all three columns to belong to $G_qS_a$ can only reduce this probability. Consequently,

whenever the target matrix has rank at least two. This estimate holds for each allowed shift, so also after averaging over $a$.

If any target column is zero, its inclusion probability is zero. Otherwise fix one target column. Its inverse image under $G_q$ is uniform among the $q^3-1$ nonzero vectors, and $S_a$ consists of $s$ nonzero vectors. Thus

This also covers all patterns of equal columns. The remaining assertions follow from the line property and short-relation conclusion in Lemma [5].

In the sampling construction, choose $(a,G_q)$ independently of all labels, all digit choices, and the random change of coordinates at the main modulus. Given $V$, choose the auxiliary residues of the sampled columns independently and uniformly from $V$. Since $|V|=s$ for every outcome, the probability of any prescribed ordered triple of auxiliary residues is

where $A$ is any integer lift of that triple. This identity includes repeated residues and is unchanged on conditioning on any main-modulus data. It is the normalization used when the two residue conditions are combined by the Chinese remainder theorem.

Sampling integral columns

We now combine the two residue constructions and lift them to integral columns. The purpose of this section is to express the probability of a small determinant as a weighted lattice count. The main and auxiliary changes of coordinates are shared by all samples; fresh labels, digits, auxiliary columns, and lifts are chosen for each sample.

Set

For $u\in\mathcal{B}$, define its projection by

Choose $G_h$ uniformly in $\mathrm{SL}_3(\mathbb{Z}/h\mathbb{Z})$, independently of the auxiliary set $V$. Conditional on $(G_h,V)$, sample columns $u\in\mathcal{B}$ independently as follows:

1. Draw a label uniformly from $K$ and its digit column $c$ by the main-modulus construction, using fresh independent digit choices. Prescribe $u\bmod h=G_hc$.

2. Independently choose $u\bmod q$ uniformly from $V$.

3. Among columns with those residues, choose $u$ uniformly in $\mathcal{B}$.

Since $h$ and $q$ are coprime and $hq$ divides $N$, each pair of prescribed residues has exactly $(N/(hq))^3$ lifts. This also shows that the sampling rule is defined for every outcome of the residue choices. The samples need not be independent after averaging over $(G_h,V)$; all estimates below retain the shared choices.

Lemma 6.1 (Proportional pairs). For two sampled columns $u,v$, one has

Proof. Equality of the projections is equivalent to proportionality of $u$ and $v$, because their third coordinates are positive. Every column in $\mathcal{B}$ is a positive integer multiple of a unique primitive integral vector $z$ with $z_3>0$. The number of its multiples in $\mathcal{B}$ is at most $\sqrt{6N}/|z|$. Therefore the total number of ordered proportional pairs in $\mathcal{B}^2$, including equal columns, is at most

For the last estimate, dyadic shells of radius $R$ contain $O(R^3)$ integral vectors and contribute $O(R)$ to the sum.

Condition on both columns’ residues at both moduli and on the shared random choices. Their lifts are independent, each uniform on exactly $(N/(hq))^3$ columns. The preceding count bounds the number of proportional pairs within any two such sets of lifts. Dividing by $(N/(hq))^6$ and averaging proves the claim. $\square$

For three samples, write $A=(u^{(1)},u^{(2)},u^{(3)})$ for the integral matrix of columns, and $C=(c^{(1)},c^{(2)},c^{(3)})$ for their digit matrix before multiplication by $G_h$. With $C$ fixed, use Lemma 4.1 to define $D,E,I=DE$ and the row lattice $\Lambda=\Lambda_C$, and write $\mathcal{O}=\mathcal{O}_C$ for the orbit in Lemma 4.2. Thus $\Lambda$ is the inverse image in $\mathbb{Z}^3$ of the row span of $C$ modulo $h$, and $\mathcal{O}=\{GC:G\in\mathrm{SL}_3(\mathbb{Z}/h\mathbb{Z})\}$. Recall also the auxiliary weight from (5.6):

Here the probability defining $W$ averages only over the auxiliary choices.

Lemma 6.2 (Exact lifting identity). Condition on all three labels and digit columns, hence on $C$. For any set $\mathcal{E} \subseteq\mathcal{B}^{3}$ of integral matrices,

Proof. The matrix $G_hC$ is uniform on $\mathcal{O}$, since every point of an orbit has the same number of group elements mapping $C$ to it. Given $V$, the three auxiliary residues are independent and uniform on its $s$ elements. Consequently, for each specified ordered triple of auxiliary residues, its probability is its inclusion probability in $V$, divided by $s^3$. This remains true when some residues coincide. Independence of the main and auxiliary choices and the exact number of lifts give, for each fixed integral $A$ with $A\bmod h\in\mathcal{O}$, the conditional probability

For other matrices the probability is zero. Summation proves the identity.

We call a sampled triple bad if its projected points are pairwise distinct and $|\det A|\leq\tau$. Every matrix in $\mathcal{O}$ has determinant $\det C$ modulo $h$. Since $2\tau<h$, at most one integer $t\in[-\tau,\tau]$ can occur as the determinant of a bad triple with $A\bmod h\in\mathcal{O}$. If the labels are all distinct, Lemma 3.3 rules out every such $t$.

The following estimate handles the one remaining determinant value. Its nonzero case follows immediately from the lattice count; the zero case requires the auxiliary construction and is proved in the next section.

Proposition 6.3 (Weighted count at a fixed determinant). Fix a digit matrix $C$, with row lattice $\Lambda$ of index $I=DE$ and special-linear orbit $\mathcal{O}$ modulo $h$. For each integer $t$ with $|t|\leq\tau$, let $\mathcal{A}_t$ consist of the matrices $A$ whose columns lie in $\mathcal{B}$, whose projected columns are pairwise distinct, and which satisfy $A\bmod h\in\mathcal{O}$ and $\det A=t$. Then

Proof. Suppose first that $t\ne0$. Since $0<|t|\leq\tau<q$, the reduction of $A$ modulo $q$ has rank three. Its columns are therefore affinely independent, and Proposition 5.3 gives $W(A)\ll1$. Every row of $A$ belongs to $\Lambda$ and has norm less than $4N$. Moreover $E\mathbb{Z}^3\subseteq\Lambda$ gives $\lambda_3(\Lambda)\leq E\leq h<4N$. Proposition 2.5, applied with $X=4N$, proves the estimate.

For $t=0$, Proposition 7.1 below proves the stronger bound $O(\log(2N)N^6/I^2)$ for all matrices with rows in $\Lambda$ and pairwise distinct projected columns. The orbit restriction only reduces this set, so it gives the claimed estimate as well.

Corollary 6.4 (Probability of a bad triple). Three sampled columns satisfy

Proof. Conditional on the labels and digit matrix $C$, the probability is zero when all labels are distinct. Otherwise Lemma 6.2 and Proposition 6.3, together with the bound $|\mathcal{O}|\gg h^8/(D^3E^2)$ from (4.2), bound it by

Let $F$ be the event that two of the three labels agree. The uniform conditional moment estimate (14) gives

This step uses the moment estimate for every fixed label triple, including repeated labels; the corresponding digit draws remain independent. Averaging the conditional bound proves the corollary.

Counting determinant-zero triples

The remaining part of the weighted count concerns collinear projected points. We organize these triples by their integral linear relation. The auxiliary modulus excludes short relations when the three residues are affinely independent. When two residues coincide, the equality usually imposes an additional lattice condition; the relations for which it does not are sufficiently sparse.

Keep the digit matrix $C$ fixed, and write $\Lambda=\Lambda_C$ for its row lattice from Lemma 4.1. Write

Thus $C$ has diagonal form $(1,D,E)$ over $\mathbb{Z}/h\mathbb{Z}$, $[\mathbb{Z}^3:\Lambda]=I$, and $E\mathbb{Z}^3\subseteq\Lambda$. Recall also $H=h^2$, $q>h^{100}$, the box $\mathcal{B}=[0,N)^2\times[N,2N)\cap\mathbb{Z}^3$, and the weight $W(A)$ from (18). For a column $u\in\mathcal{B}$, its projection means $(u_1/u_3,u_2/u_3)$.

Proposition 7.1. For the lattice $\Lambda$ and weight $W$ above, let $\mathcal{Z}$ be the set of integer $3\times3$ matrices whose columns belong to $\mathcal{B}$, whose rows belong to $\Lambda$, whose determinant is zero, and whose three projected columns are pairwise distinct. Then

The implied constant is independent of the fixed digit matrix $C$.

The orbit restriction in Proposition 6.3 only reduces this sum. We first record the lattice estimates needed for the null vectors.

Lemma 7.2. For a primitive vector $x\in\mathbb{Z}^3$, put

where $g(x)>0$. Then

The reduction of $\Lambda_x$ modulo $q$ is the entire plane

If $\Gamma\subseteq\Lambda_x$ is a sublattice of index $m$, the number of ordered triples of vectors in $\Gamma$, all of length at most $4N$ and spanning a plane over $\mathbb{Q}$, is at most

Proof. Primitivity gives $x \cdot\mathbb{Z}^{3} = \mathbb{Z}$. Since $E\mathbb{Z}^{3} \subseteq\Lambda$, we have $E\mathbb{Z} \subseteq g(x)\mathbb{Z}$, so $g(x) \mid E$. Lemma 2.3 gives the formula for $J_x$, and $g(x)^3/I \le E^2/D \le h^2$.

Primitivity also implies $\bar{x} \ne0$, with no restriction on the size of $x$. To prove surjectivity, choose $z \in\mathbb{Z}^{3}$ with $x \cdot z = 1$. If an integral lift $v$ of a point of $\Pi_x$ has $x \cdot v = qa$, then $v-qaz \in\mathbb{Z}^{3} \cap x^\perp$ is another lift of the same point. Thus $\mathbb{Z}^{3} \cap x^\perp$ reduces onto $\Pi_x$. Its multiple by $E$ lies in $\Lambda_x$ and still reduces onto $\Pi_x$, because $q \nmid E$.

Finally, a triple counted in (7.3) contains two independent vectors of length at most $4N$. Therefore the second successive minimum of $\Gamma$ is at most $4N$ whenever the count is nonzero. Lemma 2.2 then bounds the choices for each vector by $O(N^2/\det\Gamma)$, and $\det\Gamma= mJ_x$.

Lemma 7.3. For $R \ge h$,

In particular, this estimate holds when $R > H/2$.

Proof. Since $g(x) \mid B^e$, write $g(x) = B^{a(x)}$ with $0 \le a(x) \le e$. For $0 \le j \le e$, the condition $B^j \mid g(x)$ is equivalent to $Cx = 0 \pmod{B^j}$. Indeed, if $\widetilde{C}$ is any integral lift of $C$, then $\Lambda$ is the sum of the integral row span of $\widetilde{C}$ and $h\mathbb{Z}^{3}$, and $B^j \mid h$. The diagonal form of $C$ shows that the fraction of residue classes modulo $B^j$ satisfying this congruence is

Indeed, the first diagonal coordinate must vanish, the second must be divisible by $B^{\max(j-b,0)}$, and the third is unrestricted since $j \le e$.

Because $R \ge h \ge B^j$, each residue class contains $O((R/B^j)^3)$ integral vectors of length less than $2R$. We may discard primitivity for this upper bound. Consequently,

The exponents in the last sum strictly increase to $b+e$, so its bound is uniform in $B$. Finally, $h \ge2$ implies $H/2=h^2/2 \ge h$.

Proof of Proposition 7.1. Every $A \in\mathbb{Z}$ has rational rank two. Indeed, its columns are nonzero, and no two are proportional because their projections are distinct. Its right nullspace therefore has a primitive integral generator $x$, unique up to sign. Every coordinate of $x$ is nonzero: otherwise the relation would make two columns proportional. Taking the cross product of two independent rows and dividing by the gcd of its coordinates gives

Every row of $A$ lies in $\Lambda_x$ and has length at most $4N$. Thus $x$ records a relation among the columns, while the rows are lattice vectors perpendicular to $x$. We may sum over both choices of sign of $x$ for an upper bound.

Partition the possible vectors into dyadic shells $R\le\lvert x\rvert<2R$, $R=1,2,4,\ldots$. By (26), there are $O(\log(2N))$ shells. We will bound the weighted contribution of each shell by $O(N^6/I^2)$. For a fixed primitive $x$ in such a shell, a condition confining every row to an index-$m$ sublattice of $\Lambda_x$ gives at most

matrices of rational rank two, by (7.3) and $J_x=I|x|/g(x)$. In the affine case we will sum $g(x)^3$ using Lemma 7.3. In the equal-pair cases we instead use $g(x)^3\le Ih^2$, together with an extra row congruence or a smaller number of possible null vectors. The support statement and the three weight bounds in Proposition 5.3 give the following exhaustive cases.

Affinely independent residues. If $W(A)>0$ and the columns of $A$ mod $q$ are affinely independent, Lemma 5.2 excludes the relation $Ax=0$ when $|x|\le H$. To see both parts of this exclusion, if $x_1+x_2+x_3\ne0$ use the restricted shift; if the sum is zero, use affine independence and $\bar{x}\ne0$. Hence a contributing shell satisfies $R>H/2$. Using $W(A)\ll1$, (7.6) with $m=1$, and Lemma 7.3, its contribution is at most

An equal pair with an additional equation. Every other matrix of positive weight has two equal columns modulo $q$. Fix one pair $i<j$ with this property, and put $\delta=e_i-e_j$, where the $e_i$ are the standard basis vectors. Summing over the three pairs only changes the implied constant. First suppose that $\bar{x}\notin\mathbb{F}_q\delta$. The functional $v\mapsto v\cdot\delta$ is nonzero on $\Pi_x$: the annihilator of $\Pi_x$ is precisely $\mathbb{F}_q\bar{x}$. By Lemma 7.2, the rows of $A$ therefore belong to the index-$q$ sublattice

There are $O(R^3)$ integral $x$ in any shell. Using (7.6) with $m=q$, the pointwise bound $g(x)^3\le Ih^2$, and $W(A)\ll(q^3/s)^2$, the contribution is at most

Here and below we use $q^3/s\ll qH^6=qh^{12}$ and $q>h^{100}$. This argument includes matrices of every rank modulo $q$.

An equal pair without an additional equation. It remains to consider $\bar{x}\in\mathbb{F}_q\delta$. The coordinate of $x$ outside the pair $i,j$ is divisible by $q$ and, by (7.5), is a nonzero integer. Thus $|x|\ge q$, and a contributing shell has $R>q/2$. The nonzero multiples of $\delta$ give $q-1$ residue classes for $x$ modulo $q$. Each class contains $O((1+R/q)^3)$ vectors of length less than $2R$, so the number of possible $x$ in this shell is

Rank at least two modulo $q. The weight bound $W(A)\ll q^3/s$ now gives

for the contribution of the shell.

Rank at most one modulo $q$. All rows reduce into one of the $q+1$ one-dimensional linear subspaces of $\Pi_x$. This also covers the zero row space. For each such line $\ell\subseteq\Pi_x$, surjectivity in Lemma 7.2 shows that

has index $q$ in $\Lambda_x$. Formula (7.3) thus bounds the rank-two rational row triples, summed over all these lines, by

Using (7.9) and the general weight bound, the weighted contribution is at most

The affine and equal-pair cases cover the support of $W$. Their bounds are uniform over the dyadic shells, so summing over the $O(\log(2N))$ shells proves (24).

Deletion and projective normalization

The preceding estimates allow us to remove every repeated projected point and every small triangle while retaining many columns. We first construct a set for each sufficiently large prime $r$, compare its area bound with its cardinality, and then pass to every sufficiently large cardinality. All constants below may depend on the fixed integer $k$; none depends on the growing prime $r$.

This final step is an elementary alteration argument. The earlier probabilistic lower bound of Komlós, Pintz and Szemerédi [10] uses a stronger hypergraph independence lemma; no such lemma is needed below.

Proof of Theorem 1.1. Keep the parameters constructed above, with $d=41$, and set

Here $k \ge2$ and $B$ is an odd prime, so $\tau\ge1$. Take $2n_r$ samples with the shared random choices and independent conditional draws specified in Section 6. Let $Z$ count the unordered pairs of sample indices with equal projected points, plus the unordered triples whose projected points are pairwise distinct and whose determinant has absolute value at most $\tau$. Linearity of expectation, Lemma 6.1, and Corollary 6.4 give

No independence between the counted events is needed.

Both terms tend to zero. Indeed, $N=(hq)^{10}$ and $\tau\ge1$ give

For the other term, the definition of $n_r$ gives

Since $B^{k-1}\ge3$, the definition of $\tau$ implies $\tau\ge B^{k-1}/3$, and hence $h/\tau\le3B=O_k(r^{30})$. The bounds $B=O_k(r^{30})$, $q \le2h^{100}$, and $N=(hq)^{10}$ also give $\log(2N)=O_k(\log r)$. Thus the second term in (29) is $O_k((\log r)^2r^{-9})=o(1)$. Thus $\mathbb{E}Z=o(n_r)$.

For sufficiently large $r$, choose an outcome with $Z<n_r$. For each violating pair or triple in that outcome, mark one of its indices for deletion. This marks at most $Z$ indices and meets every original violation. After deleting all marked indices, at least $n_r$ remain; retain any $n_r$ of them. Their projections form a set $P_r$ of $n_r$ distinct points in $[0,1)^2$, and every triple of retained columns satisfies $|\det A|>\tau$. In particular, the construction excludes every zero-area triple as well.

For a retained triple, divide the $j$th column of $A$ by its positive third coordinate $A_{3j}$. The resulting columns have the form $(p_{j1},p_{j2},1)^{\mathsf T}$, so the determinant formula for triangle area gives the exact identity

Since $N\le A_{3j}<2N$ for each $j$, every retained triangle has area at least $\tau/(16N^3)$. Consequently

Also $\tau<h$ and $N\ge h^{10}$ give $a_r>rh^{29/2}\to\infty$. Hence $n_r\to\infty$ and eventually $n_r\ge a_r/2$. Combining this with (8.4) yields

We now express both the cardinality and the area bound in terms of $r$. The parameter choices give

Consequently, if

then

Since $a_r/2\le n_r\le a_r$ for sufficiently large $r$, there are fixed constants $A_k,D_k>0$ such that

for every sufficiently large prime $r$. In particular, put

The upper bound in (30) gives $r^2\ge D_k^{-\eta}n_r^\eta$. Combining this with (8.5), we obtain

Thus the same cardinality estimate that will permit interpolation also converts the factor $r^2$ into a fixed power of the number of points.

For a sufficiently large integer $n$, put $m=\lceil(n/A_k)^{1/\alpha}\rceil$. Lemma 3.2 supplies a prime $r$ with $m<r\le2m$. Once $(n/A_k)^{1/\alpha}\ge1$, we have $m\le2(n/A_k)^{1/\alpha}$, so (30) gives

This uses only the two-sided cardinality bounds, not monotonicity of $n_r$. Retain any $n$ points of $P_r$. Deleting points cannot decrease the minimum triangle area. Since $0 < \eta< 2$, (32) therefore yields

Taking $c_1 = c_* C_k^{-2+\eta}$ proves Theorem 1.1. All constants are absolute because $k$ is fixed independently of $r$ and $n$. The formula (31) is explicit; no attempt has been made to optimize the construction parameters.

An elementary prime-interval estimate

We prove Lemma 3.2, the form of Bertrand’s postulate used to choose the two moduli and to pass to every sufficiently large cardinality. The argument is the elementary binomial proof of Erdős [7].

Proof of Lemma 3.2. Write $P(x) = \prod_{p \le x} p$, where the product is over primes. First, $P(x) < 4^x$ for $x \ge1$. It suffices to prove this for integer $x$ by induction. The cases $x = 1, 2$ are immediate. An even integer $x > 2$ is composite, so $P(x) = P(x-1)$. For $x = 2m + 1$, every prime in $(m+1,2m+1]$ divides $\binom{2m+1}{m}$. The two central binomial coefficients are equal and their sum is strictly less than $2^{2m+1}$, whence $\binom{2m+1}{m} < 4^m$. Thus

Suppose now that there is no prime in $(n,2n]$. The largest binomial coefficient in $(1+1)^{2n}$ gives $\binom{2n}{n} \ge4^n/(2n+1)$. For any prime $p$, its exponent in this coefficient is

Each summand is zero or one, so the entire prime power contributed by $p$ is at most $2n$. The primes at most $\sqrt{2n}$ therefore contribute at most $(2n)^{\sqrt{2n}}$. Larger primes have exponent at most one. Those in $(2n/3,n]$ have exponent zero, and by assumption there are none in $(n,2n]$. For sufficiently large $n$ it follows that

Taking logarithms contradicts $(n/3)\log4 > \sqrt{2n}\log(2n) + \log(2n+1)$ for sufficiently large $n$.