================================================================================
A POWER IMPROVEMENT IN THE HEILBRONN TRIANGLE LOWER BOUND
================================================================================
A complete, self-contained proof, rewritten for a reader who knows
coordinate geometry and is willing to learn some elementary number theory.
--------------------------------------------------------------------------------
MAIN THEOREM (proved below)
--------------------------------------------------------------------------------
Let Delta(P) be the smallest area of a triangle determined by three distinct
points of a finite set P in the unit square [0,1]^2, and let Delta(n) be the
largest possible Delta(P) as P ranges over n-point subsets of [0,1]^2.
There are absolute constants eta > 0, c_1 > 0, and an integer n_0 >= 3 such
that, for every integer n >= n_0,
Delta(n) >= c_1 * n^(-2 + eta).
Consequently, for every epsilon > 0 and all sufficiently large n,
Delta(n) is NOT bounded by n^(-2 + epsilon). So the "almost n^(-2)"
formulation of the Heilbronn triangle problem is FALSE.
The exponent eta we produce is astronomically small (on the order of
2 / (45435*k + 16) for a fixed, astronomically large integer k). The point
of the theorem is only that eta > 0.
--------------------------------------------------------------------------------
HOW TO READ THIS DOCUMENT
--------------------------------------------------------------------------------
- Read section 0 (overview) and section 1 (introduction). These explain
the problem, its history, and the shape of the proof.
- Then read section 8 (deletion and scaling) and section 9 (the prime
interval), the two finishing sections that assemble the main theorem.
- Sections 2-7 are the engine room. Each begins with a short "what and
why" paragraph.
Every lemma is stated three times: a plain-English summary, a precise
mathematical statement, and a proof. If a proof feels overwhelming, read
only the headline; each section's argument is independent of the algebra
in the later sections.
--------------------------------------------------------------------------------
NOTATION
--------------------------------------------------------------------------------
Area(pqr) area of the triangle with vertices p, q, r
det(u,v,w) determinant of the 3-by-3 matrix with columns u, v, w
Delta(P) minimum of Area over triples of distinct points of P
Delta(n) maximum of Delta(P) over |P| = n and P in [0,1]^2
|x| Euclidean length of x (cardinality for a set)
[N] the set {0, 1, ..., N-1}
F_q finite field with q elements
Z/hZ integers modulo h
R^d real d-dimensional space
R^x the group of units of a ring R
det L covolume of a lattice L in its real span
A << B |A| <= C * B for some absolute constant C
(subscripts, e.g. <<_k, indicate parameter dependence)
A >> B same as B << A
A = O(B) same as A << B
A = o(B) A/B -> 0 in whatever limit is being taken
g | h g divides h
All logarithms are natural (base e). Constants in << and >> are absolute
unless explicitly subscripted, and never depend on the growing prime r on
the sampled labels, or on the sampled columns.
Now we begin.
================================================================================
SECTION 0. OVERVIEW AND THE MAIN RESULT
================================================================================
0.1 What the Heilbronn triangle problem asks
Place n points in the unit square. They determine C(n,3) = n(n-1)(n-2)/6
triangles. Some of these are small. The question Heilbronn asked in the
1950s is: what is the largest value we can force for the smallest triangle
area? Formally,
Delta(n) = max over P in [0,1]^2 with |P| = n
of min over triples {p,q,r} of P of Area(pqr).
Heilbronn conjectured Delta(n) = O(n^(-2)): no arrangement of n points
makes every triangle bigger than a constant times n^(-2).
Placing n points on a square grid with side about n^(-1/2), the smallest
triangle has area about n^(-1). Naive square grids are bad. Random points
are bad too: some triples are tiny.
0.2 What is known
Upper bounds on Delta(n):
Roth 1951 : Delta(n) = o(1/n)
Schmidt 1972, Roth 1972 : refinements
KPS 1981 : Delta(n) << n^(-8/7 + eps)
CPZ 2023 : Delta(n) <= n^(-8/7 - 1/2000) for large n
CPZ 2025 : Delta(n) << n^(-7/6 + eps) for all eps > 0
Lower bounds on Delta(n):
Random sampling + deletion: Delta(n) >> n^(-2)
KPS 1982 : Delta(n) >> (log n) / n^(-2) (disproves the
original Heilbronn conjecture)
So we know c (log n)/n^2 <= Delta(n) <= C n^(-7/6 + eps).
The question we answer: is the upper bound essentially n^(-2 + eps)?
That is, does there exist, for every eps > 0, a constant C = C(eps) with
Delta(n) <= C n^(-2 + eps) for all n?
Zakharov's 2026 survey calls this the almost n^(-2) formulation.
Our MAIN THEOREM says NO. There is an absolute eta > 0 such that, for all
sufficiently large n, Delta(n) >= c_1 n^(-2 + eta). So the almost n^(-2)
formulation is false. That is what we prove.
0.3 Strategy in seven steps
STEP 1. Work with INTEGER COLUMNS: vectors u = (u_1, u_2, u_3)^T satisfying
0 <= u_1, u_2 < N and N <= u_3 < 2N. Each column represents the point
pi(u) = (u_1/u_3, u_2/u_3) in the unit square. Three columns u, v, w form
a matrix A with columns u, v, w and give a triangle of area
|det A| / (2 A_{31} A_{32} A_{33}). (0.1)
Since N <= A_{3j} < 2N, the area is at least |det A| / (16 N^3). So if we
keep the determinant large, we keep the triangle area large.
STEP 2. Sample many integer columns at random, subject to TWO arithmetic
restrictions that make small-determinant triples rare.
Condition A (main). Give each column an independent uniform label in
the finite field F_{r^d} for a fixed odd integer d (we take d = 41).
The label determines the column modulo a prime power h = B^k (B a
large prime, k a fixed integer), by a specific digit construction. If
three labels are distinct, then det(u^(1), u^(2), u^(3)) mod h has no
small integer representative.
Condition B (auxiliary). At a second prime q much larger than h,
restrict the columns modulo q to a random affine image of a "cap" S
(a set with no three collinear points) supported in a small box.
A random shift a and a random invertible 3x3 matrix G_q turn S into a
random set V = G_q(a + S) modulo q. The result is a random cap with
no short integer relations among distinct elements.
STEP 3. Combine the two residues (mod h and mod q) via the Chinese
remainder theorem. Because h and q are coprime, each pair of prescribed
residues has exactly (N/(hq))^3 integer lifts in the box.
STEP 4. Count "bad triples" (small determinant, including zero) using
lattice geometry. The result is a probability bound of the form
Pr(bad triple among three random samples) << (log N)^2 * h / (N^3 r^d).
STEP 5. Delete one point from each bad triple. Since the expected number
of bad triples is much smaller than the sample size, most points survive.
STEP 6. The surviving points all have determinants above a threshold tau,
so their triangle areas are bounded below by tau / (16 N^3).
STEP 7. Choose the sample size so that the surviving point count matches
the target n. Pass from primes r to arbitrary integers n via Bertrand's
postulate, obtaining the main theorem with an explicit eta > 0.
The rest of the paper is the detailed proof of each step.
0.4 Other aspects of the two congruence conditions
Condition A alone leaves ONE gap: when two of the three labels coincide,
det A mod h may have a small integer representative. The number of such
triples is small (about r^(-d) of them), but that would only save a log
factor. To do better we need Condition B.
Condition B's role is subtle. It ensures that determinant ZERO -- the
case of collinear projected points -- is also rare. Three collinear
points always have determinant zero regardless of their labels, so
Condition A cannot exclude them. Condition B excludes them because
short integer relations among distinct residues mod q are impossible.
So the null vector of a singular matrix A mod q must be long, and a
long null vector requires a small number of integer matrices.
Section 7 splits this into cases:
(a) Affinely independent residues mod q: null vector x has |x| > H/2.
Lattice counting in the plane x^perp kills this case.
(b) Repeated residue columns mod q: an extra row congruence (or a
short-null-vector restriction) kills this case.
0.5 Organization
Section 1: introduction and background.
Section 2: lattice estimates: counting matrices with prescribed row bounds
and prescribed determinant.
Section 3: field norms and the first congruence condition.
Section 4: residue orbits: the diagonal form of a digit matrix mod h and
the size of its SL_3 orbit.
Section 5: the auxiliary cap: constructing V and computing its inclusion
probabilities.
Section 6: sampling: the joint probability of a small-determinant triple.
Section 7: determinant-zero triples: a separate weighted lattice count.
Section 8: deletion, scaling, and the main theorem.
Section 9: an elementary prime-interval estimate.
The two-line summary, for a reader in a hurry:
Sample integer columns with two arithmetic restrictions. Show that the
probability of a bad triple is tiny. Delete. The survivors form a point
set with minimum triangle area a positive power better than n^(-2).
Therefore Delta(n) >> n^(-2+eta).
================================================================================
SECTION 1. INTRODUCTION AND BACKGROUND
================================================================================
1.1 The problem statement
For any three points p, q, r in R^2, define
Area(pqr) = (1/2) * |det(q - p, r - p)|.
For a finite set P in R^2 with |P| >= 3, define
Delta(P) = min over unordered triples {p, q, r} of P of Area(pqr).
(A collinear triple has area zero.) For n >= 3, define
Delta(n) = max over P in [0,1]^2 with |P| = n of Delta(P).
Two sanity facts:
- The maximum defining Delta(n) EXISTS. The minimum-area function is
continuous on the compact space of ordered n-tuples of points in
[0,1]^2, and it is positive for suitable points in general position on
a parabola. A tuple with a repeated point has minimum area zero, so the
maximum is attained at a tuple of distinct points.
- Delta(P) can be zero: any three collinear points do the trick. A
maximizing configuration must therefore be in general position.
This is Heilbronn's problem. The goal is the exact growth rate of Delta(n).
1.2 The original conjecture and its failure
Heilbronn conjectured Delta(n) = O(n^(-2)). Two elementary constructions
attain Delta(n) >> n^(-2):
- Erdos's finite-field parabola (recorded in Roth 1951, Appendix). Take
points whose coordinates are rational with denominators q, built from
nonlinear functions of a small set of field elements. Determinants are
nonzero integers by the Vandermonde structure, bounded below by 1/q^2
after scaling. This gives Delta(n) >> n^(-2).
- Random sampling. Take n random points, delete one point from each small
triangle. The number of small triangles is manageable and after deletion
many points remain. Again Delta(n) >> n^(-2).
KPS (1982) improved the lower bound to Delta(n) >> (log n) / n^2, which
disproves the original Heilbronn conjecture. The argument is probabilistic
and hypergraph-theoretic: the "small triangle" hypergraph on random points
has few cycles, and an independent-set argument extracts a large subset
with no small triangles.
So the original conjecture is dead. What remains is the almost n^(-2)
question.
1.3 The almost n^(-2) formulation
Zakharov (2026) discusses the formulation:
For every epsilon > 0, there is C_epsilon and n_0(epsilon) such that
Delta(n) <= C_epsilon * n^(-2 + epsilon) for all n >= n_0(epsilon).
That is: Delta(n) is essentially at most n^(-2), up to n^epsilon. It is
consistent with the KPS lower bound, since (log n)/n^2 = o(n^(-2+eps)).
Our MAIN THEOREM disproves this. We produce an absolute eta > 0 and a
constant c_1 > 0 with
Delta(n) >= c_1 * n^(-2 + eta) for all sufficiently large n.
Then, for epsilon = eta/2,
Delta(n) / n^(-2 + eta/2) >= c_1 n^(eta/2) -> infinity,
so Delta(n) is NOT bounded by C n^(-2 + eta/2). This contradicts the almost
n^(-2) formulation at epsilon = eta/2.
1.4 Upper-bound history
Roth 1951 Delta(n) = o(1/n)
Schmidt 1972 refinement
Roth 1972a, 1972b refinements
KPS 1981 Delta(n) = O_eps(n^(-8/7 + eps))
CPZ 2023 Delta(n) <= n^(-8/7 - 1/2000) for large n
CPZ 2025 Delta(n) = O_eps(n^(-7/6 + eps))
1.5 Earlier preprints and their outstanding issues
Two prior preprints claim stronger lower bounds than ours. We discuss why
we do not rely on them:
Ellmann, version 12 (2025). Acknowledges an unproved "local uniformity"
assumption (page 3) and describes the argument as heuristic. The deletion
estimate (Theorem 4, pages 5-6) uses that unproved assumption.
Agama, version 13 (2026). Theorem 4.1 (pages 12-13) counts the center
together with the boundary points, which introduces a collinear triple
formed by the two endpoints of a diameter and their midpoint. Omitting
the center leaves the every-triple estimate unproved, because the
argument only estimates triangles formed by the center and adjacent
boundary points.
These objections concern the cited arguments, not the impossibility of the
asserted bounds. Our argument is self-contained and does not build on
either preprint.
1.6 The two congruence conditions in detail
SETUP. An integer column is a vector u = (u_1, u_2, u_3)^T with
0 <= u_1, u_2 < N and N <= u_3 < 2N. It represents the unit-square point
pi(u) = (u_1/u_3, u_2/u_3).
Three columns u^(1), u^(2), u^(3) form a matrix A = [u^(1), u^(2), u^(3)].
Their projections give a triangle of area
|det A| / (2 A_{31} A_{32} A_{33}). (1.2)
Since N <= A_{3j} < 2N, the area is at least |det A| / (16 N^3). Keeping
the determinant large therefore keeps the triangle area large.
FIRST CONGRUENCE CONDITION. Fix an odd integer d (we take d = 41), a large
prime r, and a large prime power h = B^k (B a large prime, k a fixed
integer). Every column u gets an independent uniform label xi in F_{r^d}.
The label determines u mod h by a specific construction using a field
norm. The key point: if three labels are distinct, then
det(u^(1), u^(2), u^(3)) mod h
has no integer representative in [-tau, tau], for a specific tau ~ h/2.
Why? The construction takes the finite-field norm from F_{r^d} to F_r of
the Vandermonde determinant of the three labels. It is nonzero for distinct
labels, and it is encoded as a specific coefficient of a base-B expansion.
If the determinant were small, that coefficient would vanish mod r,
contradicting the norm being nonzero.
This combines the classical "Erdos parabola" of Roth 1951 with a base-B
carry-free encoding (in spirit like the Salem-Spencer and Behrend
constructions): the designated coefficient isolates exactly the norm, so
small integer representatives of det A mod h are impossible.
SECOND CONGRUENCE CONDITION. The first condition fails when two labels
coincide. To handle that, we add a restriction at an independent large
prime q with q much larger than h (we will take q > h^100).
Fix a "cap" S in F_q^3 with no three collinear points, supported in a small
box. Choose a random shift a and a random invertible 3x3 matrix G_q, and set
V = G_q(a + S).
The result is a random cap modulo q with these properties:
- No three distinct points of V are collinear over F_q.
- With high probability over (a, G_q), there is no nonzero integer
vector x with |x| <= H (where H = h^2) and x_1 + x_2 + x_3 != 0
such that x_1 u^(1) + x_2 u^(2) + x_3 u^(3) = 0 mod q, for any three
elements u^(1), u^(2), u^(3) of V.
- If x_1 + x_2 + x_3 = 0 the same conclusion holds provided the three
columns are affinely independent.
Thus the two conditions cooperate: Condition A excludes small nonzero
determinants with distinct labels, and Condition B excludes zero
determinants (with the cheap exception of repeated labels, handled
separately).
COMBINING. Since gcd(h, q) = 1, the Chinese remainder theorem says each
pair (u mod h, u mod q) has exactly (N/(hq))^3 integer lifts in the box.
This uniformity is essential: it makes the conditional analysis on
prescribed residues clean.
The engine of the proof:
- For a triple with distinct labels, |det A| > tau. No bad triangle.
- For a triple with repeated labels, the count is small, and when the
determinant is small (including zero) the auxiliary cap restricts the
possibilities severely.
Sections 2 through 7 make this all rigorous.
1.7 The determinant-zero case
Condition A (Section 3) forces |det A| > tau when the labels are distinct.
So determinant zero can only happen with a repeated label.
For a determinant-zero matrix A, the columns are linearly dependent. Choose
a primitive integer null vector x with Ax = 0. Every row of A lies in the
plane lattice x^perp. Two subcases (Section 7):
- Affinely independent residues mod q. Then the cap hypothesis excludes
short relations, so |x| > H/2. The null vector is long, and a lattice
count bounds the number of such matrices.
- Repeated residue columns mod q. Then two columns of A are equal mod q.
This is a strong extra condition. Combined with a congruence on the
null vector x (either an extra row equation or a bounded-norm
estimate), the count is again small.
1.8 Conventions
- Lengths are Euclidean.
- A primitive integer vector has coordinates with gcd one.
- The "covolume" or "determinant" of a lattice is the volume of a
fundamental domain in its real span.
- A << B means |A| <= C*B for an absolute constant C. When the constant
depends on parameters we indicate this (A <<_k B, etc.). The constant
never depends on the growing prime r, the sampled labels, or the
sampled columns.
================================================================================
SECTION 2. LATTICE ESTIMATES
================================================================================
What this section does. We count the number of 3-by-3 integer matrices whose
rows lie in a fixed lattice, whose row norms are bounded, and whose
determinant equals a prescribed integer t. We also record plane counts
needed later when t = 0.
Why we need it. In sections 6-7 we sample integer columns and ask: how many
of them form a matrix with det A = t, for a fixed t? The answer is a
lattice-point count, and section 2 provides the bound.
About the proof style. The statements are precise, but the proofs are
elementary geometry-of-numbers. Every key step is either an observation
about Euclidean lattices or a short dyadic-shell sum.
2.1 Successive minima and their product
Let L be a Euclidean lattice of positive rank s (in R^d, usually d = 3
here). Its SUCCESSIVE MINIMA are the lengths lambda_1 <= ... <= lambda_s
defined as follows: v_1 is a shortest nonzero vector of L, and v_i is a
shortest lattice vector outside span(v_1,...,v_{i-1}).
Lemma 2.1 (successive lengths). For every Euclidean lattice L of positive
rank s,
det L <= lambda_1 * lambda_2 * ... * lambda_s <= s^(s/2) * det L.
Consequently, the lattice spanned by v_1, ..., v_s has index at most
s^(s/2) in L.
In words: the product of the successive minima is comparable to the
covolume, up to a constant depending only on the dimension.
Proof. The determinant of the lattice L_0 spanned by v_1,...,v_s is a
positive integer multiple of det L, and at most the product of the lengths
(the volume of the parallelepiped spanned by v_i is at most the product of
the side lengths). This gives the upper bound.
For the lower bound, choose orthonormal coordinates such that the first j
coordinate directions span v_1,...,v_j for every j (Gram-Schmidt order).
Let Q be the open parallelepiped of side lengths lambda_i / sqrt(s) around
the origin,
Q = { (a_1, ..., a_s) : |a_i| < lambda_i / sqrt(s) for every i }.
Suppose a nonzero lattice vector z is in Q. Let j be the last nonzero
coordinate of z. Then z does not lie in span(v_1,...,v_{j-1}), and
|z| < sqrt(sum_{i=1}^j (lambda_i/sqrt(s))^2) <= sqrt(j/s) lambda_j
<= lambda_j,
contradicting the definition of lambda_j. So no nonzero lattice vector is
in Q. Therefore the translates of Q/2 by L are pairwise disjoint. The
total volume of the part of Q/2 inside one fundamental domain of L is at
most det L, since the translates of Q/2 pack into disjoint copies of
the fundamental domain shifted by lattice points. Since
vol(Q/2) = s^(-s/2) * prod_i lambda_i, this gives
s^(-s/2) * prod_i lambda_i <= det L. QED.
2.2 Points of a plane lattice in a disk
Lemma 2.2 (points in a plane lattice). Let L be a rank-two Euclidean
lattice with successive minima lambda_1 <= lambda_2.
(a) If R >= lambda_2, any translate of L has at most C R^2 / det L
points in any disk of radius R.
(b) If R < lambda_2, the points of L in the disk of radius R around zero
lie on a line and number at most 1 + 2R/lambda_1.
In words: for "large" radii, a plane lattice is roughly uniform with density
1/det L. For "small" radii, it is one-dimensional and its points are
well-spaced along one line.
Proof of (a). Let L_0 = Z v_1 + Z v_2. A half-open fundamental parallelogram
of L_0 has diameter at most lambda_1 + lambda_2 <= 2R. For each coset of
L_0 in L, attach a copy of this parallelogram to each point of that coset
inside the disk. The attached parallelograms for a fixed coset are
pairwise disjoint (since they tile a coset-translate of R^2 by L_0
shifts), and lie in a disk of radius R + (lambda_1+lambda_2)/2 <= 3R.
Hence that coset contributes at most 9 pi R^2 / det L_0 points.
Summing over [L : L_0] cosets and using det L_0 = [L:L_0] * det L proves (a).
Proof of (b). Any lattice vector outside R v_1 has length at least
lambda_2 > R. The lattice on R v_1 is Z v_1 (a shorter generator would
contradict the choice of v_1). So the points of L in the disk are
exactly the multiples of v_1 of length at most R, which number at most
1 + 2R/lambda_1. QED.
2.3 Covolumes of integral planes
Lemma 2.3 (covolume of a lattice orthogonal to a primitive vector). Let
y be a primitive integer vector, i.e. gcd of coordinates one. Then the
lattice L_y = Z^3 intersect y^perp has determinant |y|.
More generally, if Lambda is a full-rank sublattice of Z^3 of index I, and
y · Lambda = gZ for a positive integer g, then
det(Lambda intersect y^perp) = I |y| / g.
In words: the covolume of the plane lattice orthogonal to y is proportional
to the length of y, and the constant is determined by how y acts on Lambda.
Proof. Choose u in Lambda with y · u = g. The map v -> y · v / g maps
Lambda onto Z and has kernel Lambda intersect y^perp. It splits (the map
1 -> u is a section). So a basis of the kernel together with u is a
basis of Lambda. The height of u above y^perp is g/|y|, which gives
det Lambda = det(kernel) * height of u
= det(kernel) * (g/|y|).
Therefore det(kernel) = I |y| / g. For Lambda = Z^3, primitivity gives
g = 1 (there is an integer u with y · u = 1). QED.
2.4 Unequal column bounds
The following lemma is the geometric heart of the nonzero determinant
count. It handles three rectangular column bounds R_1 >= R_2 >= R_3 that
can be very different. The hard case is when the third-column radius is
small enough that the third column can only reach one direction of its
plane.
Lemma 2.4 (unequal column bounds). Let R_1 >= R_2 >= R_3 >= 1 and let
t in Z be nonzero. The number of triples (u_1, u_2, u_3) in Z^3 such that
|u_j| <= R_j and det(u_1, u_2, u_3) = t is at most
C (R_1 R_2 R_3)^2 (log(2 R_1))^2,
with C absolute, independent of t and of the radii.
In words: a nonzero determinant pins down the columns to a lower
dimensional subvariety, and the count is essentially the "flat" bound
(R_1 R_2 R_3)^2, up to a log factor for the dyadic shell accounting.
Proof. The columns u_2, u_3 are linearly independent (their cross product
is nonzero because det A = t != 0). Choose their primitive normal y,
fixing the sign by requiring the first nonzero coordinate of y positive.
Then u_2 x u_3 = a y for some nonzero integer a, so |y| <= |u_2| |u_3|
<= R_2 R_3. If mu_1 <= mu_2 are the successive lengths of L_y, then
mu_1 <= R_3 and mu_2 <= R_2.
For fixed (u_2, u_3), the determinant equation says u_1 · y = t/a. Unless
that has an integer solution, no u_1 exists. If it does, the solutions
form a translate of L_y, and by Lemmas 2.2 and 2.3 at most C R_1^2 / |y|
satisfy |u_1| <= R_1 (the required hypothesis mu_2 <= R_2 <= R_1 holds).
For a fixed normal y, the possible u_2 (resp. u_3) with |u_2| <= R_2
(resp. |u_3| <= R_3) lying in L_y number at most C R_2^2 / |y|
(resp. C R_3^2 / |y|) by Lemma 2.2(a).
Case (mu_2 <= R_3). Then u_3 has at most C R_3^2/|y| choices, and the
bound becomes
C(R_1R_2R_3)^2 * sum_{0<|y|<=R_2R_3} |y|^(-3)
<< (R_1R_2R_3)^2 * log(2 R_2 R_3).
The sum is over integer vectors y; by dyadic shell, a shell of radius Y
has O(Y^3) vectors and contributes O(Y^3 / Y^3) = O(1) to the sum;
essentially, the full sum is log-bounded. Done for this case.
Case (mu_2 > R_3). Group normals y by dyadic parameters U, Z >= 1 with
U <= mu_1 < 2U, Z <= mu_2 < 2Z.
Lemma 2.1 gives |y| = det(L_y) = UZ up to absolute constants.
Number of normals in such a group: <= C U^4 Z^2. Indeed, choose a
shortest nonzero vector z in L_y. It is primitive in Z^3 (division by a
common divisor would give a shorter vector in L_y). Its length is in
[U, 2U), giving O(U^3) choices for z. For each z, the possible normals y
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 >= 1, and Lemma 2.1 gives
nu_2 <= nu_1 nu_2 <= 2 |z| < 4U. So nu_2 <= 4U <= 4UZ, and Lemma 2.2(a)
applied at radius 4UZ bounds the contribution by
C (UZ)^2 / |z| <= C UZ^2.
Contribution per dyadic (U, Z) group. For each such normal, all eligible
third columns u_3 lie on the line of a shortest vector of length in
[U, 2U). Lemma 2.2(b) gives at most 1 + 2 R_3 / mu_1 << R_3/U choices
(since U <= mu_1 <= R_3). So:
(C U^4 Z^2) * (R_1^2 / (UZ)) * (R_2^2 / (UZ)) * (R_3 / U)
= C R_1^2 R_2^2 R_3 U
<= C (R_1 R_2 R_3)^2.
There are O(log(2 R_3) * log(2 R_2)) dyadic groups (one log per parameter
U, Z ranging from 1 to R_3 and R_2 respectively). Combining both cases
proves the lemma. QED.
2.5 Prescribed nonzero determinant
Proposition 2.5 (fixed nonzero determinant). Let Lambda be a full-rank
sublattice of Z^3 of index I. Let X >= 2, and let lambda_3 be the third
successive length of Lambda, with lambda_3 <= X. For every nonzero
integer t, the number of 3-by-3 matrices with rows in Lambda, row lengths
at most X, and determinant t is at most
C (log(2 X))^2 * X^6 / I^2.
The constant is absolute.
In words: rows in a lattice of index I have a "quadratic" probability of
producing a prescribed determinant. The bound is X^6/I^2 up to logs,
where I^2 accounts for the density of the lattice.
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,
m = [Lambda : Lambda_0] = |det V| / I <= 3^(3/2).
Every u in Lambda has coordinates in (1/m) Z relative to the v_i basis.
If u = sum_j alpha_j v_j and |u| <= X, Cramer's rule gives
|alpha_j| <= X * prod_{i != j} lambda_i / |det V|
<= 3^(3/2) * X / lambda_j.
Map A |-> Q = m A V^{-1}. This map is injective (V is invertible) and
sends integer matrices with rows in Lambda to integer matrices. Its
effect on determinant is
det(Q) = m^3 det(A) / det(V) = m^3 t / det(V).
If m^3 t / det(V) is not an integer, there are no matrices A with the
stated properties. Otherwise, Q has determinant m^3 t / det(V) != 0, an
integer.
The j-th column of Q has length at most R_j = C_0 X / lambda_j for a
sufficiently large constant C_0. These radii satisfy R_1 >= R_2 >= R_3 >= 1.
Integrality of Lambda gives lambda_j >= 1, and Lemma 2.1 gives
R_j <= C_0 X, R_1 R_2 R_3 = C_0^3 X^3 / (lambda_1 lambda_2 lambda_3)
<= C_0^3 X^3 / I.
Apply Lemma 2.4 to Q:
#(Q) <= C (R_1 R_2 R_3)^2 (log(2 R_1))^2
<= C' X^6 / I^2 * (log(2 C_0 X))^2.
Adjusting C' and using log(2 C_0 X) << log(2 X) finishes the proof. QED.
That is all the pure lattice geometry we need. Section 3 turns to the
arithmetic input that will make determinant A mod h large.
================================================================================
SECTION 3. FIELD NORMS AND THE FIRST CONGRUENCE CONDITION
================================================================================
What this section does. We construct a random distribution of integer
columns modulo h = B^k (B a large prime, k a fixed integer) such that
any three columns with distinct finite-field labels have a determinant
residue with no small integer representative. That is the "Condition A"
of the overview.
Why this is delicate. Mod h, a small integer can be small for trivial
reasons: 0, 1, -1, 2, -2, etc. We need to design the random column so
that a "generic" small integer CANNOT appear as det(u^(1),u^(2),u^(3))
mod h. The trick is to choose the column so that the SIGN of a particular
base-B digit already forbids it.
Construction outline.
Step A. Over the finite field F_r, fix three columns. Their 3x3
determinant is a Vandermonde determinant. It is zero exactly
when the columns are linearly dependent, and otherwise nonzero.
Step B. To pass from F_r to a larger field F_{r^d} with d fixed and
large, we take the FIELD NORM of the determinant. The norm is
nonzero if and only if the determinant is nonzero. It is a
degree-d polynomial in each group of 3d variables.
Step C. Encode that degree-3d polynomial as a SPECIFIC coefficient of
a base-B expansion. Choose base-B digits c_{iv} with a specific
residue modulo r, so that after expanding det(sum c_{iv} B^v),
the coefficient of B^(k-1) evaluates to the norm of the
Vandermonde determinant on the three labels.
Step D. Show that if the determinant mod h had a small integer
representative, this coefficient would have to vanish mod r,
contradicting Step C (when the labels are distinct).
The obstruction to Step D is CARRY: the coefficient of B^(k-1) in the
determinant of the base-B expansions includes contributions from higher
terms of the determinant polynomial. We handle this by taking B very
large relative to the digit size, so the contribution of these "upper
carry" terms is dominated by the designated coefficient.
3.1 Fixed parameters
Fix the following integers, all independent of r:
d = 41
M = C(4d-1, d) = C(163, 41)
T = C(M, 3)
k = T^2 + 1
These integers are astronomically large but fixed. Everything in the
construction is polynomial in r with constants depending only on k, so
all of our << constants will be absolute (or constants depending only on
k, which is a fixed integer).
Remark. The choice d = 41 is arbitrary; any sufficiently large odd
d works (probably d = 3, but the proof is simpler when d is larger
because the "extra" degrees of freedom in F_{r^d} let us distinguish
labels with high probability). We keep d = 41 to avoid any delicate
"small d" issues.
3.2 The field K = F_{r^d}
Recall: if r is prime and d >= 1, the polynomial X^(r^d) - X in F_r[X]
splits into r^d distinct linear factors over a splitting field, and the
resulting field K has r^d elements. We use K = F_{r^d} throughout.
Facts we need:
(F1) K is a field of dimension d over F_r.
(F2) The FROBENIUS MAP sigma : K -> K, sigma(t) = t^r, is an automorphism
of K over F_r. Its d-th power is the identity. Its fixed points are
exactly F_r.
(F3) For any t in K, the product t · sigma(t) · sigma^2(t) · ... ·
sigma^(d-1)(t) = Nm_(K/F_r)(t) is in F_r. It is nonzero if and only
if t != 0.
(F4) Let beta_1, ..., beta_d be an F_r-basis of K. Every element of K
has a unique expression as sum_{nu=1}^d a_nu beta_nu with a_nu in
F_r.
We will use only these four facts.
3.3 The determinant function on K-groups
Introduce 3d variables, arranged as a 3-by-d block:
X = (X_{i nu})_{1 <= i <= 3, 1 <= nu <= d}.
For such a block, define a vector in K^3 by
Z(X) = (sum_nu beta_nu X_{1nu} , sum_nu beta_nu X_{2nu} , sum_nu beta_nu X_{3nu})^T.
For three blocks X^(1), X^(2), X^(3), let
D (X^(1), X^(2), X^(3)) = det(Z(X^(1)), Z(X^(2)), Z(X^(3))).
This determinant is in K, and it is a degree-d polynomial in each of
X^(1), X^(2), X^(3) (each entry of Z(X^(j)) is linear in X^(j), and the
determinant has degree 3 in those entries, but each entry multiplies one
beta_nu times one variable, so the whole expression is degree-d in
each group because K-rational coefficients get absorbed).
Now ext-groups: define
N (X^(1), X^(2), X^(3)) = prod_{j=0}^{d-1} sigma^j (D(X^(1), X^(2), X^(3))),
where sigma acts on coefficients of K by Frobenius and fixes every variable.
The product is fixed by sigma, hence lies in F_r. So N is an element of
F_r[X^(1), X^(2), X^(3)] (a polynomial with coefficients in F_r). It is
homogeneous of degree 1 in each variable X^(j) and total degree d in each
of the three variable groups (each factor D is linear in each group, and
the product of d such factors has degree d in each group).
3.4 N is alternating
Take two of the three groups, say X^(1) and X^(2), and transpose them. The
determinant D changes sign: D(X^(2), X^(1), X^(3)) = -D(X^(1), X^(2), X^(3)).
Frobenius sigma commutes with the sign (sigma(a+b) = sigma(a)+sigma(b) is
additive, so sigma(-x) = -sigma(x)), so each factor sigma^j(D) changes
sign. The product of d factors thus changes sign by (-1)^d, which is -1
when d is odd. Thus
N(X^(2), X^(1), X^(3)) = -N(X^(1), X^(2), X^(3)) (d odd).
Similarly for any transposition of the three groups. Whence N is
ALTERNATING as a polynomial in the three groups.
3.5 N vanishes on dependent labels
Fix labels xi_1, xi_2, xi_3 in K. Let X(xi_j) be the coefficient vector of
the vector z(xi_j) = (1, xi_j, xi_j^2)^T in the beta-basis. Then
Z(X(xi_j)) = z(xi_j), and
D(X(xi_1), X(xi_2), X(xi_3)) = det(z(xi_1), z(xi_2), z(xi_3)).
This is the Vandermonde determinant of xi_1, xi_2, xi_3 times the
determinant of the matrix of (1, xi, xi^2) in the beta basis, which is the
Vandermonde product
Vandermonde = prod_{1 <= i < j <= 3} (xi_j - xi_i).
So D = Vandermonde times a nonzero constant (the "change of basis"
determinant). The VANDERMONDE VANISHES if two of the labels coincide, and
is NONZERO if the labels are distinct. Consequently:
N(X(xi_1), X(xi_2), X(xi_3)) = Nm_(K/F_r)(Vandermonde · constant)
is nonzero if and only if xi_1, xi_2, xi_3 are pairwise distinct.
This is the key fact. In fact, we have more: N(X(xi_1), X(xi_2), X(xi_3))
is in F_r, and its numerical value mod r is the norm of a Vandermonde
product. When the three labels are distinct, the norm is nonzero in F_r,
i.e., not divisible by r as an integer.
3.6 Decomposition into monomial determinants
The norm polynomial N has a lot of monomials, but they can be grouped.
Lemma 3.1 (decomposition). There exist homogeneous degree-d polynomials
f_{ia} in F_r[X] (1 <= i <= 3, 0 <= a < T)
such that
N(X^(1), X^(2), X^(3)) = sum_{a=0}^{T-1} det( (f_{ia}(X^(j)))_{1<=i,j<=3} ).
Here X refers to the "generic" 3-by-d block, and f_{ia}(X^(j)) means f_{ia}
applied to the j-th block.
For each a, the three polynomials f_{1a}, f_{2a}, f_{3a} are of the form
f_{1a} = c_{1a} m_{p_a}, f_{2a} = m_{q_a}, f_{3a} = m_{s_a},
where m_{p_a}, m_{q_a}, m_{s_a} are three DISTINCT degree-d monomials in
the 3d variables, and c_{1a} is a scalar in F_r (possibly zero).
In words: N decomposes as a sum of T monomial-determinants. Each
determinant has three monomials sitting in the three column-positions; the
first monomial may have a scalar coefficient. This decomposition is exactly
the "sum of determinants" form we need for the base-B encoding.
Proof. List the degree-d monomials in 3d variables as m_1, ..., m_M
(so M = C(4d-1, d), matching our choice above). Expand N in products
m_p(X^(1)) m_q(X^(2)) m_s(X^(3)).
If any two of p, q, s coincide, the coefficient of this monomial must
equal its own negation under transposing the two matching groups (because
N is alternating). Since r is odd, this coefficient is zero.
For each triple 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 (for the six permutations of the three groups) with the
signs in
c_{pqs} · det( m_p(X^(1)) m_p(X^(2)) m_p(X^(3)) )
( m_q(X^(1)) m_q(X^(2)) m_q(X^(3)) )
( m_s(X^(1)) m_s(X^(2)) m_s(X^(3)) ).
Enumerate the T triples p < q < s by a in {0, ..., T-1}, and take
f_{1a} = c_{pqs} m_p, f_{2a} = m_q, f_{3a} = m_s.
The claimed form follows.
Why no division by 3!? Because we use c_{pqs} directly instead of an
averaged coefficient. This works even when r = 3 (all our r will be large
but the argument is cleaner for having no exceptional cases). QED.
3.7 The base-B encoding
Choose r a large odd prime. Let L = r^(10) and choose a prime B satisfying
B in (100 k^2 L^3, 200 k^2 L^3].
Such a B exists for all sufficiently large r by Lemma 9.1 (an elementary
form of Bertrand's postulate). Set h = B^k, tau = floor(B^(k-1) / 2).
Digit notation. We write
R_h = Z / h Z, [N; B] = {0, 1, ..., N-1} in the B-adic sense.
For each row i in {1, 2, 3} and position v in {0, ..., k-1}, we will define
a digit c_{iv} in {1, ..., L}. The digits determine a column
c_i = sum_{v=0}^{k-1} c_{iv} B^v in R_h, i = 1, 2, 3,
and the random column is c = (c_1, c_2, c_3)^T mod h.
DESIGNATED POSITIONS. For a in {0, 1, ..., T-1}, let
i_a = a, j_a = T a, ell_a = T^2 - (T+1) a.
LEMMA 3.2 (designated positions). For 0 <= a, a', a'' < T,
i_a + j_{a'} + ell_{a''} = k - 1 = T^2 if and only if a = a' = a''.
Moreover, the three sequences (i_a), (j_a), (ell_a) all lie in {0, 1, ...,
k-1} and each is strictly increasing in a within its own range; in
particular, for each a, the three positions i_a, j_a, ell_a are pairwise
distinct.
In words: the identity k - 1 = T^2 is designed so that the triple sum
i_a + j_b + ell_c can only hit the target value T^2 at the "matched" triple
a = b = c. This isolates the determinant coefficient we care about.
Proof of the matching. Rewrite i_a + j_{a'} + ell_{a''} = T^2 as
a + T a' + T^2 - (T+1) a'' = T^2
a + T a' = (T+1) a''.
Reducing mod T gives a = a'' (mod T). Since 0 <= a, a'' < T, this gives
a = a''. Substituting, a + T a' = (T+1) a, so T a' = T a, hence a' = a.
The reverse implication (a = a' = a'' giving sum T^2) is immediate.
Positions ranges: i_a = a ranges over [0, T-1], j_a = Ta over
[0, T^2 - T], ell_a = T^2 - (T+1) a ranges over [T^2 - (T+1)(T-1), T^2]
which is [T, T^2]. So ell_a is in [1, T^2]. All three are in [0, T^2] =
[0, k-1]. QED.
DIGIT CONSTRUCTION. Fix a column c. Choose a label xi uniformly from K.
Independently, for each (i, v) in {1,2,3} x {0, ..., k-1}, choose digit
c_{iv} in {1, ..., L} uniformly from the residue class modulo r specified
below:
- If (i, v) = (1, i_a) for some a, require c_{iv} = f_{1a}(X(xi)) mod r.
- If (i, v) = (2, j_a) for some a, require c_{iv} = f_{2a}(X(xi)) mod r.
- If (i, v) = (3, ell_a) for some a, require c_{iv} = f_{3a}(X(xi)) mod r.
- Otherwise, require c_{iv} = 0 mod r.
Here f_{ia} are the polynomials from Lemma 3.1, evaluated at X(xi) -
the coefficient vector of (1, xi, xi^2)^T in the beta basis.
Every residue class modulo r contains exactly L/r = r^9 elements of
{1, ..., L} (because r divides L). So every required residue has exactly
r^9 possible digits, INCLUDING the zero residue. In particular, a digit
prescribed to be zero mod r is still a positive integer (chosen from
{r, 2r, ..., L}).
Lowest digit. Since c_{i0} is in {1, ..., L} and L < B, the lowest digit
c_{i0} is not divisible by B. In particular, c_i is a unit mod B, and
hence a unit in R_h = Z/B^kZ (since it is a unit mod B and B is prime).
3.8 The determinant obstruction
We now prove the CENTRAL estimate: for distinct labels, det(c) has no
small integer representative.
Lemma 3.3 (determinant obstruction). Let C be a matrix of three columns
constructed as above, 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 the interval [-tau, tau].
In words: distinct labels force det C to be a "big" integer mod h, at
least tau ~ h/2.
Proof. Define a polynomial in one variable Y by
F(Y) = det ( sum_{v=0}^{k-1} c_{iv}^{(j)} Y^v )_{1 <= i, j <= 3}.
Expanding the determinant, F(Y) is a polynomial of degree <= 3(k-1) with
integer coefficients:
F(Y) = sum_{u=0}^{3(k-1)} gamma_u Y^u.
BOUND ON COEFFICIENTS. Fix u. In the expansion, we choose one of the six
determinant permutations, and for each of the three rows i (in the
permutation) we choose a digit position v. The monomial contributes
prod_i c_{i, v_i}^{(sigma(i))} where v_1 + v_2 + v_3 = u.
Fixing the permutation and two of the three positions v determines the
third. There are at most 6 * k * k choices for the two positions, and
each digit is at most L, so
|gamma_u| <= A_0 := 6 k^2 L^3.
THE DESIGNATED COEFFICIENT. Consider the coefficient gamma_{k-1} of
Y^(k-1) in F(Y). Expanding F by rows takes the form
gamma_{k-1} = sum over triples (v_1, v_2, v_3) with v_1 + v_2 + v_3 = k-1
of sum over permutations sigma
of sign(sigma) prod_i c_{i, v_i}^{(sigma(i))}.
Now look at this modulo r. Every digit c_{iv}^{(j)} is prescribed = 0 mod r
UNLESS (i, v) is one of the designated positions for row i. So mod r,
any term where some position v_i is not designated vanishes. The only
surviving terms have all three positions designated:
v_1 = i_a for some a, v_2 = j_{a'} for some a', v_3 = ell_{a''} for some a''.
By Lemma 3.2, the sum v_1 + v_2 + v_3 = k - 1 then forces a = a' = a''. So
modulo r,
gamma_{k-1} = sum_a sum_sigma sign(sigma) prod_i f_{i, a}(X(xi_{sigma(i)}))
= sum_a det( f_{i, a}(X(xi_j)) )_{1 <= i, j <= 3}
= N(X(xi_1), X(xi_2), X(xi_3)) by Lemma 3.1.
So gamma_{k-1} = N(X(xi_1), X(xi_2), X(xi_3)) mod r. By section 3.5, N is
NONZERO mod r when the three labels are distinct, so as an INTEGER
gamma_{k-1} is not divisible by r; in particular gamma_{k-1} != 0.
BOUND THE DETERMINANT REPRESENTATIVE. Define the integer
S_C = sum_{u=0}^{k-1} gamma_u B^u.
This is congruent to det C mod h because all coefficients gamma_u with
u >= k vanish modulo B^k = h (the terms gamma_u B^u for u >= k are
divisible by B^k = h). So S_C is a representative of det C in [-|S_C|,
|S_C|] but we want a smaller one; we now show |S_C| > tau.
BOUND S_C IN ABSOLUTE VALUE. Using the coefficient bound,
|S_C| <= sum_{u=0}^{k-1} |gamma_u| B^u <= A_0 * sum_{u=0}^{k-1} B^u
= A_0 * (B^k - 1) / (B - 1)
<= (6 k^2 L^3 / (B - 1)) * (h - 1)
<= (3/50) * (h - 1) since B - 1 >= 100 k^2 L^3
< h / 2.
BOUND S_C AWAY FROM ZERO. Similarly, bounding the "sum which excludes the
top term" gives
|sum_{u=0}^{k-2} gamma_u B^u| <= A_0 * (B^(k-1) - 1) / (B - 1)
<= (3/50) * (B^(k-1) - 1).
Since gamma_{k-1} is a nonzero integer,
|S_C| = |gamma_{k-1} B^(k-1) + sum_{u=0}^{k-2} gamma_u B^u|
>= B^(k-1) - (3/50) * (B^(k-1) - 1)
= (47 B^(k-1) + 3) / 50
> tau.
Now, every OTHER representative of det C mod h is of the form
S_C + m h for m in Z. For m != 0,
|S_C + m h| >= h - |S_C| > h - h/2 = h/2 > tau.
So ALL representatives of det C mod h have absolute value > tau. QED.
3.9 Consequence for SL_3 orbits
Lemma 3.3 has the following immediate corollary.
Corollary 3.4. Let G be any element of SL_3(R_h). If A is an integer
matrix with A mod h = G C for some digit matrix C with distinct labels,
and if |det A| <= tau, then at least two of the three labels of C
coincide.
In words: for an integer matrix with a small determinant, the three
labels MUST have a collision, provided the matrix is congruent to GC for
a digit matrix C with all-distinct labels.
Proof. Since G is invertible with det G = 1, det(GC) = det C mod h.
Lemma 3.3 says det C mod h has no representative in [-tau, tau]. But
A mod h = GC and |det A| <= tau gives a small representative, contradiction.
This corollary converts a bad triple (|det A| <= tau) into a "repeated
label" event. The probability of that event, for three independently
sampled uniform labels in F_{r^d}, is at most 3/r^d (union bound over
three pairs of labels). This is the "cheap" saving that section 4 refines
into a much stronger estimate.
That is the first congruence condition. Section 4 turns to the ALGEBRA
of the digit matrix modulo h, and to estimating the size of its SL_3 orbit.
================================================================================
SECTION 4. RESIDUE ORBITS AND THE CONDITIONAL DIGIT MOMENT
================================================================================
What this section does. We analyze the algebra of the digit matrix
C = (c^(1), c^(2), c^(3)) modulo h = B^k. Two things happen:
(a) A diagonal reduction (Smith normal form over the prime power ring
Z/B^kZ) writes C as P diag(1, D, E) Q with D, E powers of B. The
two parameters D, E control BOTH the "row lattice" of possible
integer lifts of C and the size of the SL_3 orbit through C.
(b) The parameter D (the smaller divisor) has a bounded conditional
expectation, in a strong enough form to feed the bad-triple bound
of section 6. This conditional moment is the arithmetic heart of
the "cheap" saving 3 r^(-d) that we need.
Why we need it. Section 6 wants to convert the probability of a bad
triple into a sum over integer matrices A congruent to some GC mod h. The
sum involves |O_C| in the denominator (where O_C = SL_3 orbit of C)
and the lattice-size parameter D in the numerator. Section 4 computes
both.
Throughout this section: B is a prime, k >= 1, h = B^k, R_h = Z/hZ. The
"row span" of a matrix over R_h is the R_h-submodule generated by its
rows. det L is the covolume of L in its real span.
4.1 Diagonal form over R_h
Lemma 4.1 (diagonal form and the row lattice). Let C in M_3(R_h) have at
least one unit entry. Then there exist invertible matrices P, Q in
GL_3(R_h) and integers 0 <= b <= e <= k such that
C = P diag(1, B^b, B^e) Q.
Set D = B^b, E = B^e, I = DE (all as positive integers). The subgroup
Lambda_C = { v in Z^3 : v mod h is in the R_h row span of C }
is a full-rank sublattice of Z^3 satisfying
[Z^3 : Lambda_C] = I, E Z^3 ⊆ Lambda_C.
Moreover, for 1 <= j <= k, we have b >= j IF AND ONLY IF every 2x2
minor of C vanishes modulo B^j.
In words: modulo a prime power, any matrix with at least one unit entry
reduces to a diagonal matrix with entries 1, D, E. The parameter b
(the exponent in D) measures how singular C is: b is large when many
2x2 minors vanish to high B-adic order.
Proof.
Step 1 (Diagonalization). Move a unit entry of C into position (1,1) by
row/column interchanges, multiply by the inverse of that unit, then clear
its row and column by elementary row/column operations. The result has a
unit in position (1,1) and zeros elsewhere in row 1 and column 1.
Consider the remaining 2-by-2 block. If it is zero, take b = e = k.
Otherwise it has some nonzero entry. Choose one of least B-adic valuation
b (val_B of that entry as an element of Z, taking values 0..k-1, since
we are in R_h and B^k = 0). Move it to position (2,2) by row/column
interchanges within the block. Multiply the row and column appropriately
to make the entry exactly B^b. Every other entry of the block is
divisible by B^b in R_h (by the choice of least valuation), so row and
column subtraction clear its row/column in the block. The final entry
(position (3,3)) is still divisible by B^b; scale it by the inverse of
its own unit-factor to make it B^e with b <= e <= k.
Step 2 (2x2 minors determine b). Invertible row and column operations
preserve the ideal of 2x2 minors: each new 2x2 minor of C' = PCQ is a
linear combination of old 2x2 minors of C, and the inverse operations
give the reverse inclusion. For the diagonal matrix diag(1, D, E), that
ideal is generated by the single 2x2 minor D (the (2,3)-cross one, up to
sign), namely B^b * R_h. Its image modulo B^j is zero exactly when
b >= j. So b is independent of the diagonalization choice.
Step 3 (Index and containment). Write M for the row span of C over R_h.
Left multiplication by P does not change M (P is invertible so PM has the
same row span as M). Right multiplication by Q is an automorphism of
R_h^3, and Lambda_{CQ} = Lambda_C * Q^{-1}; since Q is invertible over
R_h, this map from Z^3-lifts is a bijection. So we may assume C is
diagonal: C = diag(1, D, E).
For the diagonal matrix, M = R_h x D R_h x E R_h, which has size
|M| = h * (h/D) * (h/E) = h^3 / I.
The reduction map Z^3 -> R_h^3 sends Lambda_C isomorphically onto M, so
[Z^3 : Lambda_C] = |R_h^3| / |M| = h^3 / (h^3/I) = I.
For containment: since D | E (as integers, because b <= e), the row span
of diag(1, D, E) contains E R_h x E R_h x E R_h = E R_h^3. Right
multiplication by Q preserves E R_h^3 (Q is invertible; actually need Q's
entries on E times anything to be multiples of E, which is automatic
since E * R_h * Q-entry is in E R_h). Taking inverse images:
E Z^3 ⊆ Lambda_C. QED.
Remark. The proof allows the singular case where e = k (so E = 0 in
R_h) or b = e = k (so D = E = 0). Both cases are needed because we
count determinant-zero matrices.
4.2 Size of the SL_3 orbit
Lemma 4.2 (SL_3 orbit bound). Under the hypotheses of Lemma 4.1, define
O_C = { GC : G in SL_3(R_h) }.
There is an absolute constant c_0 > 0 such that
|O_C| >= c_0 * h^8 / (D^3 E^2).
For a uniformly chosen G in SL_3(R_h), the matrix GC is uniform on O_C.
Every matrix in this orbit has the same row span and (mod-h) determinant
as C.
In words: the SL_3 orbit of a singular matrix is surprisingly large: it
is comparable to h^8 / (D^3 E^2), which is h^8 when D = E = 1 (generic).
Proof. Let H be the stabilizer of C under left multiplication in
GL_3(R_h). Conjugation by P (the diagonalizing matrix from Lemma 4.1)
identifies H with the stabilizer of diag(1, D, E) in GL_3(R_h). Work
with the latter.
Write M for a stabilizer element, so M diag(1, D, E) = diag(1, D, E).
Column 1. M(1, 0, 0)^T equals the first column of M, and it must equal
(1, 0, 0)^T (the first column of diag(1, D, E)). So M's first column is
exactly (1, 0, 0)^T.
Column 2. M(0, D, 0)^T = D times (M's second column) = (0, D, 0)^T. So
M's second column is (0, 1, 0)^T + w_2, where each entry of w_2 is
annihilated by D, i.e. is a multiple of B^(k-b) in R_h. There are
B^b = D such multiples, so given the fixed base factor (0, 1, 0)^T, there
are at most D^3 choices for M's second column.
Column 3. Similarly M(0, 0, E)^T = E times (M's third column) =
(0, 0, E)^T, so M's third column is (0, 0, 1)^T + w_3 with each entry of
w_3 annihilated by E. Each entry has E choices, so at most E^3 choices
for M's third column.
Discarding the invertibility condition:
|H| <= D^3 E^3. (4.1)
Now the determinant image of H. For any unit u in R_h^x with
u ≡ 1 (mod h/E), the matrix diag(1, 1, u) stabilizes diag(1, D, E):
diag(1, 1, u) diag(1, D, E) = diag(1, D, uE) = diag(1, D, E)
iff h | (u - 1) E iff u ≡ 1 (mod h/E).
Count units with this property.
- If e < k: h/E = B^(k-e) >= B. The units with u ≡ 1 mod B^(k-e) are
u = 1 + t B^(k-e) for t = 0, ..., B^e - 1. Each is a unit mod h
(it is ≡ 1 mod B), so there are exactly B^e = E of them.
- If e = k: the condition is vacuous, so the count is
phi(h) = B^k (1 - B^(-1)) = (1 - B^(-1)) E.
In both cases:
|det H| / |R_h^x| >= E / h. (4.2)
Orbit-stabilizer. Write K = SL_3 ∩ H. Then |K| = |H| / |det H|, and
|SL_3| = |GL_3| / |R_h^x|. Applying orbit-stabilizer in SL_3:
|O_C| = |SL_3| / |K|
= (|GL_3| / |R_h^x|) / (|H| / |det H|)
= (|GL_3| / |H|) * (|det H| / |R_h^x|).
The first factor is the full GL_3-orbit size |GL_3 C|. Also
|GL_3| = h^9 (1 - B^(-1))(1 - B^(-2))(1 - B^(-3)) >= (21/64) h^9 for
prime B >= 2, so |GL_3 C| >= (21/64) h^9 / (D^3 E^3) by (4.1).
Multiplying by (4.2):
|O_C| >= (21/64) h^9 / (D^3 E^3) * (E / h)
= (21/64) h^8 / (D^3 E^2).
So c_0 = 21/64 works. QED.
4.3 Conditional moment of D
The parameter D from Lemma 4.1 is essential: it appears in the numer-
ator of |O_C|^(-1) and in the row lattice index. The key point is that
D has a BOUNDED conditional expectation given fixed labels, if the digits
are chosen from a large set.
Lemma 4.3 (conditional digit estimate). Let r, L be positive integers
with r >= 2, r | L, and L < B. Let L_labels be a finite label set, and
for each label lambda in L_labels and each (i, u) in {1,2,3} x {0,...,k-1},
prescribe a residue a_{iu}(lambda) in Z/rZ.
Fix any three labels lambda_1, lambda_2, lambda_3 (allowing repetitions).
Independently for every (i, j, u) in {1,2,3}^2 x {0,...,k-1}, choose
d_{iju} uniformly from
{ a in {1, ..., L} : a ≡ a_{iu}(lambda_j) (mod r) }.
Define C in M_3(R_h) by
C_{ij} = sum_{u=0}^{k-1} d_{iju} B^u (mod h).
Let b and D = B^b be as in Lemma 4.1, and put theta = B (r/L)^4. Then,
for every 1 <= j <= k,
Pr(b >= j | lambda_1, lambda_2, lambda_3) <= (r/L)^(4j).
If theta < 1, then
E[D | lambda_1, lambda_2, lambda_3] <= 1 + sum_{j=1}^k theta^j <= 1/(1-theta).
In words: given fixed labels, the "singularity parameter" D is a bounded
quantity in expectation. The bound is 1/(1-theta) with theta << 1 for the
parameters we will use.
Proof. Every prescribed digit set has exactly L/r elements (integrality
of L/r: r | L). Since the lowest digit d_{ij0} <= L < B, every entry of
C is a UNIT in R_h (its lowest digit is a unit mod B, hence C_{ij} is a
unit in Z/B^kZ).
Now fix any j in {1,...,k} and condition in addition on the complete
first column of C and the first entries of the other two columns (i.e.
C_{11}, C_{21}, C_{31}, C_{12}, C_{13}). This additional conditioning only
sharpens the bound. If b >= j, then Lemma 4.1 and the vanishing of the
2x2 minor condition give, for i, v in {2,3}:
C_{iv} ≡ C_{i1} C_{11}^{-1} C_{1v} (mod B^j).
The right side is completely determined by the additional conditioning.
So if b >= j, each C_{iv} for i, v in {2,3} is forced to lie in a
specific residue class modulo B^j. That fixes the first j base-B digits of
C_{iv}, i.e. the values of d_{iv,0}, d_{iv,1}, ..., d_{iv,j-1}.
Each d_{ivu} is distributed over L/r possible values. Fixing its value
forces it to a specific element of that set. So the probability that
b >= j is at most the probability that four independent digits
(d_{22u}, d_{23u}, d_{32u}, d_{33u}) for u = 0, ..., j-1, each hit their
prescribed values, which is at most (r/L)^(4j). The four entries use
DISJOINT digit draws, even if the labels of C coincide. So the bound
holds for every fixed triple of labels. QED for the tail bound.
The moment bound: pointwise identity
B^b = 1 + sum_{j=1}^k (B^j - B^(j-1)) * 1_{b >= j}.
Take expectations conditional on labels:
E[B^b | labels] = 1 + sum_{j=1}^k (B^j - B^(j-1)) * Pr(b >= j | labels)
<= 1 + sum_{j=1}^k (B^j - B^(j-1)) * (r/L)^(4j)
<= 1 + sum_{j=1}^k B^j * (r/L)^(4j)
<= 1 + sum_{j=1}^k theta^j.
If theta < 1, the geometric series is bounded by 1/(1-theta). QED.
4.4 Application to our parameters
For our specific choices L = r^(10) and B <= 200 k^2 L^3, we have
theta = B (r/L)^4 = B r^4 / L^4 = B r^4 / r^40 = B / r^36.
Since B <= 200 k^2 r^30, this gives
theta <= 200 k^2 r^(-6).
So for k fixed and r sufficiently large, theta is TINY. In particular,
theta < 1/2 for large enough r, which gives:
Corollary 4.4 (uniform moment bound). Suppose L = r^(10) and B is chosen
as in section 3.7, and suppose r is sufficiently large (depending only on
k). Then for every fixed triple of labels lambda_1, lambda_2, lambda_3
(allowing repetitions):
E[D | lambda_1, lambda_2, lambda_3] <= 2.
In words: D is bounded in expectation, uniformly over label triples.
Corollary 4.5 (collision contribution). Let the labels be independent
and uniform in F_{r^d}, and let E_collide be the event that at least two
of the three labels coincide. Then
E[ D * 1_{E_collide} ] <= 6 r^(-d).
Proof. Condition on the labels. Over each label triple,
E[D * 1_{E_collide} | labels] = 1_{E_collide} * E[D | labels]
<= 2 * 1_{E_collide}.
Taking expectations over labels:
E[D * 1_{E_collide}] <= 2 Pr(E_collide) <= 2 * (3/r^d) = 6 r^(-d),
where the union bound over three label-pairs gives the 3/r^d. QED.
This is the critical arithmetic estimate we need in section 6. It says: on
the (cheap) event that two labels collide, the singular-parameter D is
bounded in expectation, so it can be absorbed into the log^2 factor.
Section 5 turns to the SECOND congruence condition: the auxiliary cap at
the prime q. That is what handles determinant-zero cases.
================================================================================
SECTION 5. THE AUXILIARY CAP AND ITS INCLUSION PROBABILITIES
================================================================================
What this section does. We construct a random set V in F_q^3 with the
following property: three "random" elements of V are extremely unlikely
to satisfy any short integer relation
x_1 u^(1) + x_2 u^(2) + x_3 u^(3) = 0 over F_q^3,
|x| <= H = h^2, x_1 + x_2 + x_3 != 0.
This is the "Condition B" of the overview. Together with Condition A
(sections 3-4), it is the second ingredient of the argument.
Why we need it. Condition A excludes small determinants when the three
labels are distinct. It cannot exclude determinant ZERO, because three
collinear points are collinear regardless of their labels. Condition B
breaks the tie. It makes short integer relations impossible, so a
determinant-zero matrix must have a long null vector (|x| > H), and
section 7 shows that a long null vector forces a very restrictive row
lattice.
Construction outline.
Step A. Choose an auxiliary prime q ~ h^100.
Step B. Choose a "cap" S in F_q^3 (no three collinear points) with
support in a small box, using an elliptic quadric (Barlotti).
Step C. Choose a random restricted shift a and a random invertible
3x3 matrix G_q, and set V = G_q(a + S). The result is a
random cap with strong "short-relation exclusion".
Step D. Compute the "weight" W(A) = (q^3/s)^3 * Pr(columns of A in V)
and prove three bounds that section 6 will use.
5.1 Parameters
Retain h >= 2. Choose a prime q with
H = h^2, h^100 < q <= 2 h^100, w = floor(q / (1000 H^2)).
Lemma 9.1 (Bertrand) supplies such a q for all sufficiently large h.
These choices give
q / (2000 H^2) <= w <= q / (1000 H^2),
in particular q >= 2000 H^2 >= 2000 H (since H >= 1).
We identify {0, 1, ..., w-1} with the corresponding elements of F_q.
5.2 The cap
Lemma 5.1 (Barlotti cap). For every odd prime q and every integer
1 <= w <= q, there is a set S in {0, 1, ..., w-1}^3 (a subset of F_q^3)
of size |S| >= w^3/q with no three distinct collinear points.
In words: a small "cap" in a small corner of F_q^3.
Proof. Choose a nonsquare nu in F_q and put
Q(x, y) = x^2 - nu y^2,
Gamma = { (x, y, Q(x, y)) : x, y in F_q }.
The form Q vanishes only at (0, 0). Indeed, if Q(x, y) = 0 with y != 0,
then (x/y)^2 = nu, contradicting nu being a nonsquare. If y = 0, then
x = 0 as well.
We claim Gamma has no three collinear points.
Non-vertical line case: let the line have direction (v_1, v_2, v_3) with
(v_1, v_2) != (0, 0). Parametrize it as
t |-> (x_0 + t v_1, y_0 + t v_2, z_0 + t v_3). Membership in Gamma becomes
z_0 + t v_3 = Q(x_0 + t v_1, y_0 + t v_2),
which is a quadratic equation in t with leading coefficient
Q(v_1, v_2) != 0. A nonzero quadratic has at most two roots, so the line
meets Gamma in at most two points.
Vertical line case: direction (0, 0, v_3) with v_3 != 0. The line is
(x_0, y_0, z_0 + t v_3); it meets Gamma at the unique t with
z_0 + t v_3 = Q(x_0, y_0). So at most one point.
Thus Gamma and every translate b + Gamma have no three collinear points.
For a uniform b in F_q^3, each point of F_q^3 lies in b + Gamma with
probability |Gamma| / q^3 = q^2/q^3 = 1/q. Hence
E_b [ |(b + Gamma) intersect {0,...,w-1}^3| ] = w^3/q.
Some b attains at least this average. Take S = (b + Gamma) intersect
{0, 1, ..., w-1}^3 for that b. QED.
Fix one such set S. Write s = |S|. From Lemma 5.1,
s >= w^3 / q >= q^2 / (2000^3 H^6). (5.1)
For parameters q ~ h^100 and H = h^2, this lower bound is roughly
h^188 / constant, so s is ENORMOUS compared to any fixed power of h
needed below.
The set S is FIXED before any random choices are made.
5.3 The allowed shift and the short-relation exclusion
For t in F_q, write ||t||_q for the least absolute value of an integer
representative of t. Define the set of allowed shifts
A = { a in F_q^3 : ||m a_1||_q > 3 H w for every 1 <= m <= 3H }.
We will choose a uniformly from A, and G_q uniformly from GL_3(F_q).
Lemma 5.2 (allowed shifts exist in abundance). The set A has size at
least q^3 / 2.
In words: the short-shift restriction excludes less than half of F_q^3.
Proof. For each m in {1, ..., 3H}, the "bad" values of a are those with
||m a_1||_q <= 3 H w. Since 1 <= m <= 3H < q (from q >= 2000 H >= 3H),
multiplication by m is a bijection of F_q. So m a_1 is uniform in F_q,
and ||m a_1||_q <= 3 H w holds for at most 6 H w + 1 values of m a_1.
Thus, for this m, the fraction of a in F_q^3 with a "bad" value is at
most (6 H w + 1) / q. Union over m:
Pr_{a in F_q^3}(a not in A) <= 3H (6 H w + 1) / q.
Now 6 H w + 1 <= 6 H q / (1000 H^2) + 1 = 6 q/(1000 H) + 1. Multiplying
by 3H:
3H(6 H w + 1) <= 18 H q/(1000 H) + 3 H = 18 q / 1000 + 3 H.
And 3 H <= 3 H q / (2000 H^2) * ... = 3 q/(2000 H) <= 3 q / 2000 (since
H >= 1). So
Pr(a not in A) <= 18/1000 + 3/2000 = 39/2000 < 1/2,
because 39/2000 = 0.0195 is much less than 1/2. Hence |A| >= q^3 / 2. QED.
Now the key lemma, which is what Condition B actually gives us.
Lemma 5.3 (short-relation exclusion). Let H >= 1 be an integer, q an odd
prime with q >= 2000 H^2, and w = floor(q / (1000 H^2)). Suppose S in
{0, ..., w-1}^3 has no three distinct collinear points. Choose a
uniformly from A, G_q uniformly from GL_3(F_q), and set V = G_q(a + S).
Then V has exactly s = |S| elements, contains 0 nowhere (0 is not in V),
and contains no three distinct collinear points. Moreover, if
x = (x_1, x_2, x_3) in Z^3 \ {0} satisfies |x| <= H, then for any three
distinct u^(1), u^(2), u^(3) in V:
- If x_1 + x_2 + x_3 != 0, the relation x_1 u^(1) + x_2 u^(2) + x_3 u^(3)
= 0 in F_q^3 is IMPOSSIBLE.
- If x_1 + x_2 + x_3 = 0, the relation is also IMPOSSIBLE (in fact for
ANY affinely independent triple u^(1), u^(2), u^(3) in V).
Proof. All the claimed properties are preserved under invertible linear
maps, so it suffices to prove them for T = a + S.
Cardinality and 0 not in T. If a + v = 0 for some v in S, then
||a_1||_q = ||v_1||_q <= w - 1 <= 3 H w (since w >= 1 and H >= 1),
contradicting the definition of A with m = 1. So 0 is not in T, and
|T| = |S| = s.
No three collinear points in T. Translates of S inherit the cap property.
Short-relation exclusion. Suppose there is a relation
x_1 u^(1) + x_2 u^(2) + x_3 u^(3) = 0
with |x| <= H and (say) x nonzero. Write u^(i) = G_q(a + v^(i)) with
v^(i) in S. Let m = x_1 + x_2 + x_3.
Case m != 0. Then 1 <= |m| <= 3H. Applying G_q^{-1} to the relation gives
x_1(a + v^(1)) + x_2(a + v^(2)) + x_3(a + v^(3)) = 0,
i.e. m a + x_1 v^(1) + x_2 v^(2) + x_3 v^(3) = 0. Taking first
coordinates:
m a_1 = - (x_1 v^(1)_1 + x_2 v^(2)_1 + x_3 v^(3)_1).
The right side, using integer representatives 0 <= v^(i)_1 < w, is an
integer with absolute value at most 3 H (w - 1) < 3 H w. Since
||m a_1||_q = |||m| a_1||_q (because if t has an integer representative
in [-N, N], then |m| t has a representative in [-|m| N, |m| N]; and t is in
F_q so |||m| a_1||_q = ||m a_1||_q by the field structure), this gives
||m a_1||_q <= 3 H w, contradicting a in A.
Case m = 0. Substitute x_3 = -x_1 - x_2. The relation becomes
x_1 (u^(1) - u^(3)) + x_2 (u^(2) - u^(3)) = 0 in F_q^3.
Since x is nonzero, |x_i| <= H < q, so x_1 and x_2 cannot both vanish
in F_q. If x_1 = 0 and x_2 != 0, then u^(2) = u^(3), contradicting
distinctness. Similarly for x_2 = 0 and x_1 != 0. If both nonzero, the
vectors u^(1) - u^(3) and u^(2) - u^(3) are linearly dependent over F_q,
contradicting the cap property (any three distinct elements of V are
affinely independent). QED.
5.4 The weight W and its three bounds
For an integer 3-by-3 matrix A, define the WEIGHT
W(A) = (q^3 / s)^3 * Pr( all columns of A mod q lie in V ). (5.2)
The probability averages over (a, G_q) with S fixed. W(A) measures how
much more likely it is for A to land in V^3 than it would for a random
triple from F_q^3 (which has baseline probability (s/q^3)^3):
W(A) = Pr(A mod q in V^3) / (s / q^3)^3.
Proposition 5.4 (weight bounds). With absolute implied constants:
W(A) << 1 if the columns of A mod q are affinely
independent;
W(A) << q^3 / s if rank(A mod q) >= 2;
W(A) << (q^3 / s)^2 for every integer A.
If W(A) > 0, then no column of A mod q is zero, and either (a) the
columns of A mod q are affinely independent, or (b) A has two equal
columns mod q.
In words: the first bound says "generic" triples are no more likely than
baseline. The second says "rank-two" triples are (q^3/s)-lucky. The third
says "any" triple is at most (q^3/s)^2-lucky. The (q^3/s) factor is
enormous (s >> q), so all three bounds are strong.
Proof. Replace the restricted shift a in A by an UNCONDITIONAL uniform
shift a_tilde in F_q^3. Conditioning back on a in A increases the
probability of any event by at most 2 (since |A| >= q^3/2). Write
V_tilde = G_q(a_tilde + S).
Affinely independent case. Let the columns of A mod q be affinely
independent. The affine group AGL_3(F_q) = { x |-> G_q x + b } acts
transitively on ordered affinely-independent triples in F_q^3, whose
number is q^3 (q^3 - 1)(q^3 - q). The stabilizer of a specific ordered
affinely-independent triple (W_1, W_2, W_3) consists of affine maps
with G_q W_i + b = W_i for i = 1, 2, 3. Given such a triple, the
directions W_1 - W_3 and W_2 - W_3 span a plane; a stabilizer element
must fix that plane pointwise, and its action on a complementary
direction is free. Thus the stabilizer has size about q^3.
Consequently, the probability that a random affine map sends the three
target columns to any triple inside S is
s (s - 1)(s - 2) * (size of stabilizer) / |AGL_3(F_q)|
= s(s-1)(s-2) / (q^3 (q^3-1)(q^3-q)) * 1 (up to the same q^3
cancellation).
In the notation above, the probability that a random affine map carries
the three columns of A into S equals s(s-1)(s-2) / (q^3(q^3-1)(q^3-q))
(the number of "good" affine maps divided by the total). Thus
Pr(all columns of A in V_tilde) <= 2 * s(s-1)(s-2) / (q^3(q^3-1)(q^3-q))
<< s^3 / q^9.
Multiplying by (q^3/s)^3 = q^9/s^3,
W(A) << 1.
Rank >= 2 case. Now suppose rank(A mod q) >= 2. Two of the columns, say
A_1 and A_2, are linearly independent mod q. For fixed allowed a, the
inverse images G_q^{-1}(A_1) and G_q^{-1}(A_2) are uniform among ordered
independent pairs (of which there are (q^3-1)(q^3-q) in F_q^3). Such a
pair lies in (a + S)^2 for at most s^2 choices. So
Pr(first two columns of A in V_tilde) <= 2 * s^2 / ((q^3-1)(q^3-q))
<< s^2 / q^6.
Requiring the third column also in V_tilde only decreases this. So
W(A) <= 2 * (q^3/s)^3 * s^2/q^6 << q^3/s.
General case. For any A, if some column of A is zero mod q, then that
column cannot lie in V_tilde (which contains no zero); the probability
is zero. Otherwise, fix one nonzero column, say A_1. Its inverse image
G_q^{-1}(A_1) is uniform among the q^3 - 1 nonzero vectors, and
(a + S) consists of s nonzero vectors. Thus
Pr(A_1 in V_tilde) <= 2 * s / (q^3 - 1).
So
W(A) <= 2 * (q^3/s)^3 * s/(q^3-1) << (q^3/s)^2.
The support statement (no zero column, affinely independent or repeated
columns) follows from Lemma 5.3. QED.
Remark. The three bounds prefigure exactly what we need in section 7.
- The "W(A) << 1" bound handles affinely independent triples, which
are exactly the ones where short relations are forbidden.
- The "W(A) << q^3/s" bound handles rank-2 triples with at least one
extra row equation available.
- The "W(A) << (q^3/s)^2" bound handles everything else (repeated
columns, etc.).
5.5 The normalization identity
For the sampling construction of section 6, we choose (a, G_q)
INDEPENDENTLY of all labels, all digit choices, and G_h. Given V, choose
the auxiliary residues of sampled columns independently and uniformly
from V. Since |V| = s for every outcome, the probability of any prescribed
ordered triple of auxiliary residues is
Pr(all three in V) / s^3 = W(A) / q^9, (5.3)
where A is any integer lift of that triple. The identity is unchanged on
conditioning on any main-modulus data.
In words: W(A)/q^9 is the probability that a specific residue triple
A mod q appears in V^3. This is the normalization we use in section 6,
when we combine the two congruences by the Chinese remainder theorem.
Section 6 now assembles all of this into a probability bound for "bad"
triples.
================================================================================
SECTION 6. SAMPLING INTEGRAL COLUMNS
================================================================================
What this section does. We define the random distribution of integer columns
that the whole construction uses. Each column carries:
- a finite-field label xi in F_{r^d} and a digit column c in R_h^3
satisfying the constraints of section 3, and
- an auxiliary residue u mod q chosen uniformly from the cap V of
section 5.
We combine the two residues modulo h and q by the Chinese remainder
theorem, then lift uniformly to a common box B. This gives each column a
joint distribution that we can analyze.
The section's main goal is the "bad triple" bound (Corollary 6.4): the
probability that three random columns form a matrix with pairwise distinct
projections and small determinant is at most (log N)^2 h / (N^3 r^d).
Why the sampling is easy to analyze. The two residue choices (mod h and
mod q) are independent. Their moduli h and q are coprime. So by CRT, each
pair of prescribed residues is compatible with EXACTLY (N/(hq))^3 columns
in the box B. This uniformity is the whole reason the analysis works.
6.1 The box and the sampling rule
Set
N = (h q)^10,
B = ( [0, N)^2 x [N, 2N) ) intersect Z^3.
For u in B, define its projection
pi(u) = (u_1/u_3, u_2/u_3) in [0, 1)^2.
The box is designed so that every u in B has 0 <= u_1, u_2 < N and
N <= u_3 < 2N. So pi(u) is indeed in [0, 1)^2 and the third coordinate
u_3 is comparable to N.
Choose G_h uniformly from SL_3(R_h), independently of V. Conditional on
(G_h, V), sample columns u in B independently as follows:
(1) Draw a label xi uniformly from K = F_{r^d} and its digit column
c = (c_1, c_2, c_3) in R_h^3 by the section 3 construction. The
digit column depends only on xi and fresh independent digit choices.
(2) Prescribe u mod h = G_h c.
(3) Independently choose u mod q uniformly from V.
(4) Among the columns in B whose residues modulo h and q match the
prescribed ones, choose u uniformly at random.
Since gcd(h, q) = 1 and h q divides N (because N = (h q)^10), the CRT
guarantees exactly (N/(h q))^3 lifts of each pair of residues. This makes
step (4) well-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 explicitly.
Notation for triples. For three sample columns, write
A = (u^(1), u^(2), u^(3)) integer 3-by-3 matrix of columns
C = (c^(1), c^(2), c^(3)) digit 3-by-3 matrix mod h
xi_1, xi_2, xi_3 the labels in F_{r^d}
With C fixed, define via Lemma 4.1 the diagonal parameters D, E and
I = DE; the row lattice Lambda = Lambda_C; and the special-linear orbit
O = O_C = { GC : G in SL_3(R_h) } in M_3(R_h).
6.2 Proportional pairs
The first thing to exclude is u and v having the same projection. Since
u_3, v_3 > 0, the equality pi(u) = pi(v) means u and v are proportional
over Q.
Lemma 6.1 (proportional pairs). For two sampled columns u, v,
Pr( pi(u) = pi(v) ) << (h q)^6 / N^3.
In words: proportional pairs are extremely unlikely among independently
sampled columns, so we can delete one point from each such pair at
negligible cost.
Proof. Take any two integers u, v in B with pi(u) = pi(v). They are
necessarily proportional as vectors (both have positive third coordinate).
Every u in B is a POSITIVE integer multiple t z of a UNIQUE primitive
integer vector z with z_3 > 0. The multiplier t satisfies
|t z| = t |z| <= sqrt(3) N (since |u| <= sqrt(3 N^2) roughly), so
t <= sqrt(3) N / |z|. That is, the number of multiples of z in B is at
most sqrt(3) N / |z|.
The total number of ORDERED proportional pairs in B x B (including
u = v) is therefore at most
sum over primitive z with 0 < |z| <= sqrt(3) N
(sqrt(3) N / |z|)^2
<= 3 N^2 * sum_{0 < |z| <= sqrt(3) N} |z|^{-2}
<< N^3.
The last inequality follows by dyadic shell: a shell of radius R contains
O(R^3) integer vectors, each contributing R^{-2}, so the shell total is
O(R), and summing over O(log N) shells gives O(N).
Now condition on both columns' residues at both moduli, on G_h, and on V.
Their lifts in B are independent, each uniform on exactly (N/(h q))^3
columns. The proportional-pair count above, restricted to any two
specified lift sets, bounds the number of proportional pairs by << N^3.
Dividing by (N/(h q))^6 and averaging proves the claim. QED.
6.3 The exact lifting identity
The next lemma expresses the probability of a triple event in terms of
the auxiliary weight W from section 5 and the orbit size |O_C| from
section 4. This is where the CRT uniformity and the two congruences are
combined.
Lemma 6.2 (exact lifting identity). Condition on the three labels and on
the three digit columns, hence on C. For any set E of integer matrices
in B^3,
Pr(A in E | C, labels) = (h^9 / (N^9 |O_C|))
* sum over A in E with A mod h in O_C of W(A). (6.1)
In words: the probability of a triple event is a sum of weights over the
integer matrices A that are congruent to some G C mod h and lie in B^3.
Proof. Given C and the labels, the residue u^(j) mod h is uniform on the
orbit O_C (because G_h is uniform in SL_3(R_h) and the map G |-> G C is
surjective onto O_C with each fiber of the same size). Given V, the
three auxiliary residues u^(j) mod q are independent and uniform on the
s elements of V (also independent of the main-modulus data).
Fix any specific A in B^3. For this A to be a sample, its residues must
match. Concretely, given V, the conditional probability that A's three
auxiliary residues appear is the weight divided by s^3 times the q^9
normalization:
Pr(A mod q in V^3) / s^3.
And the conditional probability that A mod h is G_h C is 1/|O_C| when
A mod h is in O_C and zero otherwise. So the conditional probability of
A given (C, labels, V) is
(1/|O_C|) * Pr(A mod q in V^3) / s^3 * (h q / N)^9.
The last factor (h q / N)^9 accounts for the CRT lift: given both residues,
the probability of picking this exact A among the (N/(h q))^3 lifts of each
of the three columns is ((h q)/N)^9.
Rewrite the middle factor:
Pr(A mod q in V^3) / s^3
= (q^9 / s^3) * Pr(A mod q in V^3) / q^9
= W(A) / q^9. (by the definition of W in 5.2)
So the conditional probability of A given (C, labels) is
(1/|O_C|) * W(A) / q^9 * (h q / N)^9 = h^9 W(A) / (N^9 |O_C|).
Summing over A in E with A mod h in O_C gives the claimed identity. QED.
6.4 Bad triples
Call a triple of samples BAD if
- its three projections pi(u^(1)), pi(u^(2)), pi(u^(3)) are pairwise
distinct, and
- |det A| <= tau,
where tau = floor(B^(k-1)/2) from section 3.7. Observe 2 tau < B^(k-1) < h,
so at most one integer t in [-tau, tau] can occur as determinant of a bad
triple with A mod h in a specific orbit O_C. By Corollary 3.4, if the
labels are all DISTINCT, then no such t exists. So a bad triple must have
at least two labels equal.
Proposition 6.3 (weighted count at a fixed determinant). Fix a digit
matrix C with row lattice Lambda = Lambda_C of index I = D E, and
special-linear orbit O_C. For each integer t with |t| <= tau, let A_t
consist of the matrices A whose columns lie in B, whose projected columns
are pairwise distinct, and which satisfy A mod h in O_C and det A = t.
Then
sum over A in A_t of W(A) << (log(2 N))^2 * N^6 / I^2. (6.2)
In words: the weighted count of matrices with a prescribed determinant
is the lattice count from section 2, weighted by the auxiliary cap.
Proof. This is exactly the place where the auxiliary cap (section 5) and
the lattice count (section 2) meet.
Case t != 0. Because 0 < |t| <= tau < q, the reduction A mod q has rank
three. So the columns of A mod q are affinely independent, and
Proposition 5.4 gives W(A) << 1.
Every row of A lies in Lambda (by the definition of Lambda as the inverse
image of the row span of C mod h) and has norm less than 4 N (since each
coordinate of A is between -2N and 2N). Moreover, E Z^3 is contained in
Lambda by Lemma 4.1, so the third successive length of Lambda is
lambda_3 <= E <= h < 4 N. Then Proposition 2.5 (fixed nonzero determinant),
applied with X = 4 N, gives
#(A in A_t) << (log(2 N))^2 * (4 N)^6 / I^2
<< (log(2 N))^2 * N^6 / I^2.
Combining W(A) << 1 finishes the t != 0 case.
Case t = 0. The stronger statement for t = 0 is Proposition 7.1 below,
which proves the bound O(log(2 N) * N^6 / I^2) for ALL matrices with
rows in Lambda and pairwise distinct projected columns. The additional
restriction A mod h in O_C only reduces the set, so it gives the claimed
bound. QED.
Now we can bound the probability of a bad triple.
Corollary 6.4 (probability of a bad triple). Three sampled columns satisfy
Pr(pi(u^(1)), pi(u^(2)), pi(u^(3)) pairwise distinct, |det A| <= tau)
<< (log(2 N))^2 * h / (N^3 r^d). (6.3)
In words: the chance that a random triple is bad is tiny: it is
(log N)^2 times h / (N^3 r^d). Since N = (h q)^10 is astronomically
larger than h, this is negligibly small.
Proof. Condition on the three labels and on C. By the "distinct labels"
case of the argument (Corollary 3.4 and the remark at the start of
section 6.4), the conditional probability is zero when the three labels
are pairwise distinct. So consider outcomes on which at least two labels
coincide.
By Lemma 6.2 with E = A_t for the appropriate t,
Pr(A in A_t | C, labels) = (h^9 / (N^9 |O_C|)) * sum_{A in A_t} W(A).
Applying Proposition 6.3 and the orbit bound |O_C| >= c_0 h^8 / (D^3 E^2)
from Lemma 4.2:
Pr(A in A_t | C, labels)
<= (h^9 / (N^9 |O_C|)) * (log(2 N))^2 * N^6 / I^2
<< (h^9 / N^9) * (D^3 E^2 / h^8) * (log(2 N))^2 * N^6 / (D^2 E^2)
= (log(2 N))^2 * h^1 * D / N^3.
So the conditional probability is << (log(2 N))^2 * h D / N^3.
Let F be the event that at least two of the three labels coincide. The
uniform conditional moment estimate (Corollary 4.4) gives, for every
fixed label triple,
E[ D 1_F | labels] <= 2 * 1_F,
and hence
E[ D 1_F ] <= 2 Pr(F) <= 6 r^(-d) (6.4)
(by the union bound over three label pairs).
Averaging the conditional probability over labels and using (6.4):
Pr(bad triple) << (log(2 N))^2 * h / N^3 * E[D 1_F]
<< (log(2 N))^2 * h / N^3 * r^(-d).
This is (6.3). QED.
The rest of the argument is bookkeeping. Section 7 handles the
determinant-zero Proposition 7.1 that Corollary 6.4 relies on. Section 8
does the deletion and scaling; section 9 the prime interval.
================================================================================
SECTION 7. DETERMINANT-ZERO TRIPLES
================================================================================
What this section does. We prove Proposition 7.1 below: the weighted sum
of determinant-zero matrices (with pairwise distinct projected columns)
is O(log(2 N) * N^6/I^2). This is exactly the missing t = 0 case of
Proposition 6.3. Together with section 6, it completes the "small
determinant" counting.
Why this is the delicate case. Condition A (sections 3-4) is silent on
determinant zero, because three collinear points are collinear regardless
of their labels. Condition B (the cap) is what breaks the tie. It excludes
short integer relations, so a determinant-zero matrix has a LONG null
vector (|x| > H), and a long null vector forces a tiny row lattice, which
forces a small count.
But the short-relation exclusion only applies when three residues mod q
are AFFINELY INDEPENDENT. If two are equal mod q, we must handle them
separately, either by an extra row equation (case B1) or by showing the
null vector must be even longer (case B2). Both cases use the weaker
weight bounds from Proposition 5.4.
7.1 Setup and statement
Keep parameters from sections 3-6:
h = B^k, H = h^2,
q prime with h^100 < q <= 2 h^100,
w = floor(q/(1000 H^2)),
N = (h q)^10,
B = [0, N)^2 x [N, 2N) intersect Z^3,
S the fixed cap in {0,...,w-1}^3, s = |S| >= q^2/(2000^3 H^6),
W(A) the auxiliary weight from section 5.4.
Keep the digit matrix C FIXED throughout, with parameters D, E, I = DE
from Lemma 4.1, row lattice Lambda = Lambda_C (index I in Z^3, contains
E Z^3), and special-linear orbit O_C with |O_C| >= c_0 h^8/(D^3 E^2).
For u in B, pi(u) = (u_1/u_3, u_2/u_3). A matrix A in Z^{3x3} has ROWS
IN LAMBDA if each row of A lies in Lambda, and COLUMNS IN B if each column
of A lies in B.
Proposition 7.1 (weighted zero count). Let Z be the set of integer 3x3
matrices with:
- columns in B,
- rows in Lambda,
- determinant zero,
- pairwise distinct projected columns.
Then
sum over A in Z of W(A) << log(2 N) * N^6 / I^2. (7.1)
The implied constant is absolute.
In words: even in the worst case (determinant zero), the weighted sum is
bounded by the same N^6/I^2 as the nonzero case, up to logs.
7.2 Plane lattices from null vectors
The first ingredient is a description of the integer plane orthogonal to
a primitive integer vector, intersected with Lambda.
Lemma 7.2 (plane lattice). Let x in Z^3 be a PRIMITIVE integer vector.
Define
Lambda_x = Lambda intersect x^perp, (a full-rank lattice in x^perp)
g(x): x · Lambda = g(x) Z, (an integer, >= 1)
J_x = det(Lambda_x). (covolume in the plane)
Then:
(a) g(x) | E, and J_x = I |x| / g(x), and g(x)^3 / I <= h^2.
(b) Lambda_x reduces modulo q to the WHOLE plane
Pi_x = { v in F_q^3 : v · x_bar = 0 }, x_bar = x mod q != 0.
(c) If Gamma subset Lambda_x is a sublattice of index m, the number of
ordered triples of vectors in Gamma, all with norm at most 4 N and
spanning a plane over Q, is at most
C N^6 / (m J_x)^3.
In words: (a) is a covolume formula; (b) says the plane lattice "spreads
out" modulo q; (c) counts plane-spanning triples.
Proof of (a). Since x is primitive, x · Z^3 = Z (there is u with x · u = 1).
Since Lambda contains E Z^3, the image x · Lambda contains E Z. Therefore
g(x) divides E (because g(x) Z contains E Z, so g(x) | E as integers).
Lemma 2.3 gives J_x = I |x| / g(x). For the last inequality:
g(x)^3 / I = g(x)^3 / (D E) <= E^3 / (D E) = E^2 / D <= E^2 <= h^2,
using D >= 1 and E <= h = B^k (from e <= k).
Proof of (b). x_bar != 0 in F_q^3 because x is primitive, so x_bar has a
nonzero coordinate mod q. Take any v_bar in Pi_x, i.e. x · v_bar = 0 mod q.
Lift to an integer v arbitrarily. Then x · v = q a for some integer a.
Take v_0 lifting v_bar to an integer. Since v_bar in Pi_x means x · v_0
is a multiple of q in Z, write x · v_0 = q a_0 for some integer a_0.
Choose z with x · z = 1 (possible because x is primitive). Then
v = v_0 - q a_0 z
satisfies x · v = q a_0 - q a_0 · 1 = 0 exactly, and v is congruent to v_0
mod q, so v is an integer lift of v_bar in Z^3 intersect x^perp.
So Z^3 intersect x^perp reduces onto Pi_x. Then Lambda_x = Lambda intersect
x^perp contains E (Z^3 intersect x^perp), so its reduction contains
E Pi_x = Pi_x (since E is a unit mod q: q doesn't divide E because
q > h >= E). Thus Lambda_x mod q = Pi_x.
Proof of (c). Suppose a triple (v_1, v_2, v_3) in Gamma with |v_i| <= 4 N
and rational rank two (i.e. not all coplanar in a specific sense - any
two are independent over Q). Then some pair, say v_1 and v_2, is linearly
independent over Q. In particular, the second successive minimum lambda_2
of Gamma is at most max(|v_1|, |v_2|) <= 4 N. So by Lemma 2.2(a), the
number of choices for v_1 in Gamma with |v_1| <= 4 N is at most
C (4 N)^2 / det Gamma (once v_2 is fixed), and similarly for v_2, v_3.
By dyadic shell over determinant parameters (as in the proof of Lemma 2.4),
this gives at most C N^6 / (det Gamma)^3 = C N^6 / (m J_x)^3. QED.
7.3 The moment sum
For the "affinely independent residues" case below, we need to sum g(x)^3
over many primitive x in a dyadic shell. The following is the key estimate.
Lemma 7.3 (moment). For any real R >= h,
sum over primitive x in Z^3 with R <= |x| < 2R of g(x)^3
<< R^3 I. (7.2)
In particular, the bound holds when R > H/2 = h^2/2.
Proof. From Lemma 7.2(a), g(x) divides E = B^e, so g(x) = B^{a(x)} for an
integer 0 <= a(x) <= e.
Key observation. For 0 <= j <= e, the condition B^j | g(x) is equivalent
to C x === 0 (mod B^j). Indeed, Lambda = (integral row span of C_tilde) +
h Z^3 for an integral lift C_tilde of C, and B^j | h. So x in Lambda mod
B^j (which is what determines whether B^j | g(x)) is the same as
C_tilde x === 0 mod B^j, i.e. C x === 0 mod B^j.
Modulo B^j, the diagonal form C = diag(1, B^b, B^e) reduces the equation
C x ≡ 0 (mod B^j) to three scalar conditions:
x_1 ≡ 0 (mod B^j),
B^max(j-b, 0) | x_2,
(no constraint on x_3, since j <= e implies B^j | B^e).
So exactly B^(2j - max(j-b, 0)) of the B^(3j) residue classes modulo B^j
satisfy C x ≡ 0 mod B^j.
For any radius rho and any j in [0, e], the number of integer vectors x
with |x| < rho and B^j | g(x) is at most the fraction of "good" residue
classes times the volume of the ball:
#{x : |x| < rho and B^j | g(x)}
<< rho^3 * (B^(2j - max(j-b, 0)) / B^(3j))
= rho^3 * B^(-j - max(j-b, 0)).
Taking rho = 2 R and summing per shell:
#{x in shell : B^j | g(x)} << R^3 * B^(-j - max(j-b, 0)).
Since g(x) = B^a(x) with 0 <= a(x) <= e, we bound
g(x)^3 <= sum_{j=0}^{e} B^(3j) 1_{B^j | g(x)}
(the right side is a geometric "cover" of B^(3a(x))). Summing over x in
the shell:
sum of g(x)^3 over x in shell
<= sum_{j=0}^{e} B^(3j) * #{ x in shell : B^j | g(x) }
<= sum_{j=0}^{e} B^(3j) * (32/3 pi) R^3 * B^(-j - max(j-b,0))
= (32/3 pi) R^3 * sum_{j=0}^{e} B^(2j - max(j-b, 0)).
The exponent 2j - max(j-b, 0) is:
~ j + b for j > b (since 2j - (j-b) = j + b)
~ 2j for j <= b (since 2j - 0 = 2j)
The sum over j is dominated by the largest exponent. As j ranges in [0, e]:
for j in [0, b]: B^(2j), sum ~ B^(2b) (geometric).
for j in [b+1, e]: B^(j+b), sum ~ B^(e+b) (geometric).
So the total sum is O(B^(2b) + B^(e+b)) = O(B^(e+b)) since b <= e and
B is large. And B^(e+b) = B^b * B^e = D * E = I.
So:
sum of g(x)^3 over shell <= (32/3 pi) R^3 * O(I) = O(R^3 I).
This is (7.2). QED.
7.4 Proof of Proposition 7.1
Every A in Z has RATIONAL RANK TWO. Why?
- Its columns are nonzero (each has positive third coordinate).
- Its determinant is zero (by hypothesis).
- No two columns are proportional (their projections are distinct: if
u, v are columns and pi(u) = pi(v), then u_3 v = u v_3 as vectors,
so u and v are proportional).
So the columns span a two-dimensional subspace of Q^3.
The RIGHT NULLSPACE of A is therefore one-dimensional and contains a
PRIMITIVE integer vector x (unique up to sign). Every coordinate of x is
NONZERO: if x_1 = 0, then x_2 u^(2) + x_3 u^(3) = 0 (from Ax = 0),
so u^(2), u^(3) are Q-proportional (contradicting distinct projections);
if x_2 = 0, then x_1 u^(1) + x_3 u^(3) = 0, so u^(1), u^(3) proportional
(same contradiction); if x_3 = 0, then x_1 u^(1) + x_2 u^(2) = 0, same.
So x_1 x_2 x_3 != 0.
Bounding the SIZE of x. Taketwo independent rows u_row_i and u_row_j of A.
Their cross product u_row_i x u_row_j is a nonzero multiple of x (since
A has rank 2 and x is the unique primitive null vector). Dividing by the
gcd of its coordinates gives x itself. So
|x| <= |u_row_i| |u_row_j| / gcd <= (4 N)(4 N) / 1 = 16 N^2. (7.4)
Partition the possible x into DYADIC SHELLS R <= |x| < 2R, with
R = 1, 2, 4, .... By (7.4), there are O(log(16 N^2)) = O(log N) shells.
We prove that each shell contributes at most C N^6/I^2 to the weighted
sum, and then sum over O(log N) shells.
Fix a shell R <= |x| < 2R. We split into three cases according to the
behaviour of A mod q.
Case A: Affinely independent columns of A mod q.
Suppose A has W(A) > 0 and its three columns are affinely independent
mod q. Then by Lemma 5.3, no relation Ax = 0 mod q can hold with |x| <= H.
So the shell can only contribute if R > H/2, i.e., if R is "large".
For such a shell, Proposition 5.4 gives W(A) << 1 (affinely independent
bound). And the rows of A, being in Lambda intersect x^perp = Lambda_x,
must number at most C N^6 / J_x^3 by Lemma 7.2(c) with m = 1 (the triple
of rows spans a rational plane, because the rank of A is exactly 2).
So for one specific x in the shell:
# of A with null vector x <= C N^6 / J_x^3 = C N^6 g(x)^3 / (I^3 |x|^3)
<= C N^6 g(x)^3 / (I^3 R^3).
Weighted by W(A) << 1:
sum over A with null vector x of W(A) <= C N^6 g(x)^3 / (I^3 R^3).
Summing over x in the shell (using Lemma 7.3):
contribution of shell <= (C N^6 / (I^3 R^3)) * (C' R^3 I)
= C'' N^6 / I^2.
So each shell in case A contributes << N^6/I^2. QED for case A.
Case B: Two equal columns of A mod q.
Every other matrix A in Z with W(A) > 0 must have two EQUAL columns
mod q. Fix one such pair i < j, put delta = e_i - e_j (the i-th minus
the j-th standard basis vector), and reduce to this single pair (there
are three pairs to consider; we take one).
Let x be the primitive null vector of A. We look at x mod q as an element
x_bar = x mod q of F_q^3.
The ANNIHILATOR of Pi_x = {v : v · x_bar = 0} in F_q^3 is exactly the
one-dimensional subspace F_q x_bar (the "geometric dual" of Pi_x). The
functional v |-> v · delta vanishes on Pi_x iff delta in F_q x_bar (by the
definition of annihilator).
Subcase B1: x_bar NOT in F_q delta.
Then v |-> v · delta is a NONZERO functional on Pi_x, so it vanishes on a
hyperplane of Pi_x, which is a codimension-1 subspace (a "line" in the
plane Pi_x).
Every row v of A satisfies v · delta = A_{k i} - A_{k j} = 0 mod q
(because columns i and j of A are equal mod q). So all rows lie in the
sublattice
{ v in Lambda_x : v · delta = 0 mod q }.
Since the reduction Lambda_x mod q = Pi_x (Lemma 7.2(b)) and v |-> v · delta
is surjective from Pi_x onto F_q, this sublattice has index q in Lambda_x.
So (7.3) with m = q:
# of A with null vector x <= C N^6 / (q J_x)^3.
Weighted by the general (weakest) bound W(A) << (q^3/s)^2:
sum over A for this x of W(A) <= C N^6 / (q J_x)^3 * (q^3/s)^2.
Rewrite 1/(q J_x)^3 = g(x)^3 / (q^3 I^3 |x|^3) <= I h^2 / (q^3 I^3 R^3) =
h^2 / (q^3 I^2 R^3). So
per-x weighted <= C N^6 h^2 / (q^3 I^2 R^3) * q^6 / s^2
= C N^6 h^2 q^3 / (I^2 R^3 s^2).
Sum over O(R^3) vectors x in the shell:
contribution of shell <= C N^6 h^2 q^3 / (I^2 s^2).
Now use s >= q^2/(2000^3 H^6), i.e. 1/s^2 <= 2000^6 H^12 / q^4:
contribution <= C' N^6 h^2 H^12 / (I^2 q)
= C' N^6 h^26 / (I^2 q)
<< N^6 / I^2, since q > h^100 >> h^26.
So case B1 also contributes << N^6/I^2 per shell. QED for case B1.
Subcase B2: x_bar IN F_q delta.
Then delta in F_q x_bar. Write delta = (e_i - e_j) with {i, j, k} = {1, 2, 3}
distinct. Since delta = c x_bar for some c in F_q^×, we get
x_bar_i = c, x_bar_j = -c, x_bar_k = 0.
The third coordinate: x_k === 0 mod q. Since x_k != 0 as an integer
(shown above), this means q | x_k, so |x_k| >= q. Hence |x| >= q, and a
contributing shell must satisfy R >= q/2.
Also, x_bar ranges over q - 1 nonzero multiples of delta mod q. Each class
contains at most O((R/q + 1)^3) integer vectors of length less than 2 R.
So
# of x in shell with x_bar in F_q delta << R^3 / q^2. (7.5)
We further split by rank of A mod q.
Subcase B2a: rank(A mod q) >= 2.
Then W(A) << q^3/s (Proposition 5.4, rank >= 2 bound). And (7.3) with
m = 1 (no extra row equation available now; the equal-pair condition
is already "absorbed" into x in this subcase):
# of A with null vector x <= C N^6 / J_x^3 <= C N^6 g(x)^3 / (I^3 R^3)
<= C N^6 I h^2 / (I^3 R^3)
= C N^6 h^2 / (I^2 R^3).
Weighted by W(A) << q^3/s:
per-x weighted <= C N^6 h^2 / (I^2 R^3) * q^3/s.
Sum over << R^3/q^2 vectors x (from (7.5)):
contribution of shell <= C N^6 h^2 / (I^2 R^3) * q^3/s * R^3/q^2
= C N^6 h^2 q / (I^2 s).
Now s >= q^2/(2000^3 H^6), so 1/s <= 2000^3 H^6 / q^2:
contribution <= C' N^6 h^2 H^6 / (I^2 q)
= C' N^6 h^14 / (I^2 q)
<< N^6 / I^2, since q > h^100 >> h^14.
So subcase B2a also gives << N^6/I^2. QED for B2a.
Subcase B2b: rank(A mod q) <= 1.
Then all rows of A reduce into a single one-dimensional linear subspace of
Pi_x (of which there are q + 1, including {0}).
For each such line ell in Pi_x, the preimage
{ v in Lambda_x : v mod q in ell }
has index q in Lambda_x. Indeed, Lambda_x reduces onto Pi_x (Lemma 7.2(b))
via a surjective map Lambda_x -> Pi_x. The line ell is a one-dimensional
subspace of the two-dimensional space Pi_x, i.e. a codimension-1 subspace
of Pi_x. The preimage of a codimension-1 subspace under a surjective map
has index q. So m = q, and (7.3) applies.
per-x, per-line <= C N^6 / (q J_x)^3.
Sum over q + 1 lines:
per-x, rank <= 1 <= C' (q+1) N^6 / (q J_x)^3
<= C' N^6 / (q^2 J_x^3) (since (q+1)/q^3 <= 2/q^2)
Weighted by W(A) << (q^3/s)^2:
per-x weighted <= C' N^6 / (q^2 J_x^3) * q^6/s^2
= C' N^6 q^4 / (J_x^3 s^2).
Now J_x^3 = (I |x|/g(x))^3 >= I^3 R^3 / g(x)^3, and g(x)^3 <= I h^2, so
1/J_x^3 <= g(x)^3 / (I^3 R^3) <= I h^2 / (I^3 R^3) = h^2 / (I^2 R^3).
So:
per-x weighted <= C' N^6 q^4 h^2 / (I^2 R^3 s^2).
Sum over << R^3/q^2 vectors x (from (7.5)):
contribution of shell <= C' N^6 q^4 h^2 / (I^2 R^3 s^2) * R^3/q^2
= C' N^6 q^2 h^2 / (I^2 s^2).
Now s >= q^2/(2000^3 H^6), so 1/s^2 <= 2000^6 H^12 / q^4:
contribution <= C'' N^6 q^2 h^2 * 2000^6 H^12 / (I^2 q^4)
= C'' N^6 h^2 H^12 / (I^2 q^2)
= C'' N^6 h^26 / (I^2 q^2)
<< N^6 / I^2, since q^2 > h^200 >> h^26.
So subcase B2b also gives << N^6/I^2. QED for B2b.
Combining all cases. The three cases A, B1, B2 cover the entire support of
W (by Proposition 5.4: any A with W(A) > 0 has no zero column and either
affinely independent columns or two equal columns). Every shell R >= 1
contributes << N^6/I^2. Summing over O(log N) shells gives
sum over A in Z of W(A) << log(2 N) * N^6 / I^2. (7.6)
This is (7.1). QED.
Section 8 now does the deletion and scaling: choose many samples, delete
one point per bad triple, and prove that most points survive with every
triangle area at least tau/(16 N^3).
================================================================================
SECTION 8. DELETION AND SCALING
================================================================================
What this section does. We complete the proof of the main theorem. We
combine all the estimates from sections 2-7 into a single construction
that produces, for every sufficiently large prime r, a set P_r of n_r
points in [0, 1)^2 such that
every triple of distinct points of P_r has area at least tau/(16 N^3).
Then we relate n_r to the exponents and to n, and get the main theorem.
Why this is the "easy" endgame. Every estimate is already in place. The
only new observation is that we can choose 2 n_r samples, that the
expected number of "bad" events is much less than n_r, and that after
deletion of one point per bad event, n_r points still survive.
8.1 Sample size and bad events
Keep all parameters from sections 3-7:
d = 41, M = C(163, 41), T = C(M, 3), k = T^2 + 1,
B a prime with 100 k^2 L^3 < B <= 200 k^2 L^3 (L = r^10),
h = B^k, tau = floor(B^{k-1}/2), H = h^2,
q a prime with h^100 < q <= 2 h^100, w = floor(q/(1000 H^2)),
N = (h q)^10, B_box = [0, N)^2 x [N, 2N) intersect Z^3,
S fixed in {0, ..., w-1}^3, s = |S| >= q^2/(2000^3 H^6).
Fix r a sufficiently large prime. Define the sample size
a_r = r * sqrt(N^3 / tau), n_r = floor(a_r). (8.1)
Since k >= 2 and B is an odd prime, tau >= 1. So n_r -> infinity as
r -> infinity.
Sample 2 n_r columns by the section 6 rule, using shared random choices
G_h, V for all 2 n_r samples and independent conditional draws for each
sample.
Define the random variable Z as
Z = #{ unordered pairs {u^(i), u^(j)} of samples with
pi(u^(i)) = pi(u^(j)) }
+ #{ unordered triples {u^(i), u^(j), u^(k)} of samples with
pi(u^(i)), pi(u^(j)), pi(u^(k)) pairwise distinct and
|det A| <= tau }.
Z counts every "bad" event.
8.2 Expected number of bad events
Lemma 8.1 (linearity of expectation). For every sufficiently large prime r,
E[Z] / n_r << n_r (h q)^6 / N^3 + n_r^2 (log(2 N))^2 h / (N^3 r^d). (8.2)
In words: we only use linearity of expectation. There is no independence
assumption between the bad events.
Proof. By linearity of expectation,
E[Z] = C(2 n_r, 2) * Pr(pi(u) = pi(v))
+ C(2 n_r, 3) * Pr(bad triple, pairwise distinct projections).
Here C(2 n_r, 2) << n_r^2 and C(2 n_r, 3) << n_r^3. By Lemma 6.1
(proportional pairs) and Corollary 6.4 (bad triples),
Pr(pi(u) = pi(v)) << (h q)^6 / N^3,
Pr(bad triple) << (log(2 N))^2 h / (N^3 r^d).
So
E[Z] << n_r^2 (h q)^6 / N^3 + n_r^3 (log(2 N))^2 h / (N^3 r^d).
Divide by n_r to get (8.2). QED.
Lemma 8.2 (both terms in (8.2) tend to zero).
Proof. Term 1 of (8.2):
n_r (h q)^6 / N^3 <= r tau^{-1/2} (h q)^6 / N^{3/2}
using n_r <= a_r = r sqrt(N^3/tau). With N = (h q)^{10} so N^{3/2} =
(h q)^{15},
(h q)^6 / N^{3/2} = (h q)^{-9}.
So
Term 1 <= r tau^{-1/2} (h q)^{-9} <= r (h q)^{-9}.
Since h q >= h >= B^2 grows polynomially in r, term 1 -> 0 as r -> infinity.
Term 2 of (8.2):
n_r^2 (log(2 N))^2 h / (N^3 r^d)
<= (r^2 N^3/tau) * (log(2 N))^2 h / (N^3 r^d)
= (log(2 N))^2 * (h/tau) / r^{d-2}.
Since B^{k-1} >= 3 (from B >= 100 k^2 L^3 >= 100), the floor in tau
gives tau >= B^{k-1}/3, hence
h/tau <= 3B.
Since B <= 200 k^2 r^{30},
Term 2 <= (log(2 N))^2 * 600 k^2 r^{30} / r^{d-2}
= 600 k^2 (log(2 N))^2 r^{32-d}.
With d = 41, we have 32 - d = -9, so
Term 2 <= 600 k^2 (log(2 N))^2 r^{-9} -> 0.
Both terms tend to zero. QED.
Combining Lemmas 8.1 and 8.2:
E[Z] = o(n_r). (8.3)
8.3 Deletion
Since E[Z] = o(n_r), there exists an outcome with Z < n_r for all
sufficiently large r. Fix such an outcome.
For each violation counted by Z (each bad pair or triple), mark one of
its points (say, the smallest-index point in the violation). Let M be
the set of marked points. Since there are Z violations and each marks
exactly one point, |M| <= Z < n_r.
Delete all marked points. The remaining samples number at least
2 n_r - Z > 2 n_r - n_r = n_r. Retain any n_r of them. Let P_r be the
set of their projections in [0, 1)^2.
By construction:
- |P_r| = n_r.
- No two points of P_r share a projection (all such pairs had one
endpoint deleted).
- Every triple of distinct points of P_r has p - Every triple of distinct points of P_r has pairwise distinct
projections and |det A| > tau.
The last bullet is the crucial one: every bad triple has been broken by
the deletion of at least one of its points.
8.4 Area lower bound from determinant
From section 1.6, a triangle with integer columns u^(1), u^(2), u^(3)
and matrix A has area
Area(pi(u^(1)), pi(u^(2)), pi(u^(3))) = |det A| / (2 A_31 A_32 A_33).
Since all columns have third coordinate A_{3j} in [N, 2N), we have
A_{3j} < 2N and hence
Area >= |det A| / (2 (2N)^3) = |det A| / (16 N^3).
Combined with |det A| > tau for every distinct triple of P_r:
Area >= tau / (16 N^3) for every triple of distinct points of P_r.
So
Delta(P_r) >= tau / (16 N^3). (8.4)
8.5 Conversion to the exponent -2 + eta
Now we express both Delta(P_r) and n_r as powers of r.
Step 1 (r^2 vs n_r^2 Delta). Since tau < h and N >= h^10,
a_r = r sqrt(N^3/tau) > r sqrt(h^{30}/h) = r h^{29/2} -> infinity,
so n_r = floor(a_r) >= a_r/2 for sufficiently large r. Combined with
(8.4):
n_r^2 Delta(P_r) >= (a_r/2)^2 tau / (16 N^3)
= (r^2 N^3 / tau)/4 * tau / (16 N^3)
= r^2 / 64.
So
n_r^2 Delta(P_r) >= r^2/64. (8.5)
Step 2 (cardinality growth). Recall the parameter ranges
B in (100 k^2 r^30, 200 k^2 r^30],
h = B^k,
q in (h^100, 2 h^100],
N = (h q)^10,
tau = floor(B^(k-1)/2) in [B^(k-1)/3, B^(k-1)/2].
We express each of these as a power of r up to a constant depending only
on k. Write <<_k << and >>_k >> for inequalities where the implied constant
depends only on k.
- B ~_k r^30.
- h ~_k r^{30 k}.
- q ~_k h^100 ~_k r^{3000 k}.
- h q ~_k r^{3030 k}.
- N ~_k (h q)^10 ~_k r^{30300 k}.
- N^3 ~_k r^{90900 k}.
- tau ~_k B^{k-1} ~_k r^{30 (k-1)}.
- N^3 / tau ~_k r^{90900 k - 30 (k-1)} = r^{90870 k + 30}.
- sqrt(N^3/tau) ~_k r^{(90870 k + 30)/2} = r^{45435 k + 15}.
- a_r = r sqrt(N^3/tau) ~_k r^{45435 k + 16}.
- n_r = floor(a_r), so n_r ~_k r^{45435 k + 16}.
Define
alpha = 45435 k + 16.
Then there are positive constants A_k, D_k depending only on k such that,
for every sufficiently large prime r,
A_k r^alpha <= n_r <= D_k r^alpha. (8.6)
8.6 Delta(P_r) as a power of n_r
Combine (8.5) and (8.6). From (8.6) the upper bound gives
r^2 >= D_k^{-2/alpha} n_r^{2/alpha} = D_k^{-eta} n_r^eta,
where
eta = 2 / alpha. (8.7)
Combined with (8.5):
n_r^2 Delta(P_r) >= r^2/64 >= D_k^{-eta} n_r^eta / 64.
Divide by n_r^2:
Delta(P_r) >= (D_k^{-eta}/64) n_r^{-2 + eta}.
Set c_* = D_k^{-eta} / 64 > 0. Then
Delta(P_r) >= c_* n_r^{-2 + eta} for every sufficiently large
prime r. (8.8)
This is the main inequality, stated for prime r only.
8.7 From primes to all n
Let n be an arbitrary sufficiently large integer. Set
m = floor( (n / A_k)^{1/alpha} ) + 1,
so that m >= (n/A_k)^{1/alpha}, i.e.
A_k m^alpha >= n. (8.9)
Since alpha > 0, m -> infinity with n. So for n sufficiently large,
m >= 2, and Lemma 9.1 (Bertrand, section 9) supplies a prime r with
m < r <= 2 m.
Why is Bertrand applicable? Because we need a prime in (m, 2m] for every
integer m >= 2, which is exactly Bertrand's postulate.
Apply (8.6) to this prime r. Using m < r <= 2m and A_k m^alpha >= n:
n_r >= A_k r^alpha > A_k m^alpha >= n.
So n_r >= n. Also, we will need an upper bound on n_r in terms of n.
From r <= 2 m and m <= 2 (n/A_k)^{1/alpha} (which holds because
m = floor((n/A_k)^{1/alpha}) + 1 <= (n/A_k)^{1/alpha} + 1 <= 2
(n/A_k)^{1/alpha} for n large):
n_r <= D_k r^alpha <= D_k (2 m)^alpha
<= D_k 2^alpha 2^alpha (n/A_k)
= (D_k 4^alpha / A_k) n.
Define
C_k = max(1, D_k 4^alpha / A_k).
Then
n <= n_r <= C_k n. (8.10)
Now take any n points of P_r. Since |P_r| = n_r >= n, this is possible.
Taking a subset cannot decrease the minimum triangle area, so
Delta(subset of P_r of size n) >= Delta(P_r)
>= c_* n_r^{-2 + eta}
>= c_* (C_k n)^{-2 + eta}
= c_* C_k^{-2 + eta} n^{-2 + eta}.
Set
c_1 = c_* C_k^{-2 + eta} = D_k^{-eta} C_k^{-2 + eta} / 64 > 0.
Since k is a fixed integer (independent of r and n), and D_k, C_k, alpha,
eta depend only on k, c_1 is an absolute constant. We have thus proved
Delta(n) >= c_1 n^{-2 + eta} for every sufficiently large integer n.
This is exactly the main theorem, with eta = 2/(45435 k + 16).
8.8 Why the exponent eta is positive but tiny
For concreteness, plug in k = T^2 + 1 with T = C(M, 3) and M = C(163, 41).
Then M is around 10^47, T is around 10^93, k is around 10^187. So
alpha = 45435 k + 16 is astronomically large, and eta = 2/alpha is
correspondingly astronomically small.
The theorem guarantees SOME positive power of n. It does not attempt to
optimize the exponent. A better analysis of the auxiliary-cap construction
could shrink d and k dramatically (to perhaps d = 3 and k = 2), giving a
much less absurd eta. But the paper's goal is to establish the qualitative
result, not the best possible n^eta.
The end of the proof. Section 9 supplies the Bertrand postulate we used.
================================================================================
SECTION 9. AN ELEMENTARY PRIME-INTERVAL ESTIMATE
================================================================================
What this section does. We prove a form of Bertrand's postulate: for every
integer m >= 2, there is a prime p with m < p <= 2m.
Why we need it. Three uses:
- Section 3.7: to choose the prime B with 100 k^2 L^3 < B <= 200 k^2 L^3.
- Section 5.1: to choose the prime q with h^100 < q <= 2 h^100.
- Section 8.7: to pass from "Delta(n_r) for prime r" to "Delta(n) for
every sufficiently large n".
The argument is the elementary binomial proof of Erdos (1932).
Lemma 9.1 (Bertrand). For every integer m >= 2, there is a prime p with
m < p <= 2m.
Proof. Let n be an integer >= 2. We prove there is a prime in (n, 2n].
The statement for m = n follows by renaming.
Step 1 (small n checked directly). For 2 <= n <= N_0 (with N_0 = 100, say),
a prime in (n, 2n] can be exhibited explicitly. So we may assume n >= N_0
for the analytic part of the argument.
Step 2 (binomial lower bound). The sum of the coefficients in (1+1)^{2n}
is 4^n, distributed among 2n+1 coefficients. The largest coefficient is
the central one, C(2n, n). So
C(2n, n) >= 4^n / (2n+1). (9.1)
Step 3 (exponent of a prime). For any prime p, the exponent of p in
C(2n, n) = (2n)! / (n!)^2 is
v_p(C(2n, n)) = sum over j >= 1 of (floor(2n/p^j) - 2 floor(n/p^j)). (9.2)
For any real x, floor(2x) - 2 floor(x) is either 0 or 1. So each summand
is 0 or 1. The sum stops once p^j > 2n, giving at most log_p(2n) + 1
nonzero summands. We therefore have
p^{v_p(C(2n, n))} <= 2n for every prime p. (9.3)
Step 4 (bound on the product of small primes). Define P(x) as the product
of all primes p <= x. Standard induction gives
P(x) <= 4^{x-1} for every integer x >= 2. (9.4)
Indeed, by induction on x: the product P(2n)/P(n) of primes in (n, 2n]
divides C(2n, n), and C(2n, n) < 4^n (binomial sum bound), so
P(2n)/P(n) < 4^n. Combined with P(2n) = P(n) * (P(2n)/P(n)) and the
induction hypothesis for P(n), we get P(2n) < 4^{n} * 4^{n-1} = 4^{2n-1}.
For odd x, P(x) = P(x-1) < 4^{x-2} < 4^{x-1}.
Step 5 (splitting the binomial). Splitting C(2n, n) into contributions
from primes p <= sqrt(2n) and from larger primes:
- Contribution from p <= sqrt(2n): by (9.3), each such prime contributes
at most 2n. There are at most sqrt(2n) such primes, so the total is
at most (2n)^{sqrt(2n)}.
- Contribution from p > sqrt(2n): then p^2 > 2n, so v_p <= 1 (at most
one factor of p in C(2n, n) for such p, since only floor(2n/p) -
2 floor(n/p) at j = 1 is possibly nonzero; higher powers exceed 2n).
Every p in (sqrt(2n), 2n/3] contributes at most one factor, and by
assumption there are NO primes in (n, 2n]. Primes in (2n/3, n]
contribute nothing (each has floor(2n/p) = 2 and floor(n/p) = 1).
So the total large-prime contribution is at most P(2n/3).
Combining with (9.1) and (9.4):
C(2n, n) <= (2n)^{sqrt(2n)} P(2n/3) < (2n)^{sqrt(2n)} 4^{2n/3}.
Step 6 (contradiction). Combine with the lower bound (9.1):
4^n / (2n+1) < (2n)^{sqrt(2n)} 4^{2n/3}.
Taking log base e:
n log 4 - log(2n+1) < sqrt(2n) log(2n) + (2n/3) log 4.
Rearranging:
(n/3) log 4 < sqrt(2n) log(2n) + log(2n+1). (9.5)
The right side is O(sqrt(n) log n) as n -> infinity. The left side is
(n/3) log 4 = omega(n), which dominates any O(sqrt(n) log n) for n large.
So (9.5) is FALSE for all sufficiently large n. This contradiction proves
there is a prime in (n, 2n] for n >= N_0, which is what we wanted. QED.
That is the last section. The whole proof is now assembled.
================================================================================
WHAT WE HAVE PROVEN
================================================================================
Main theorem (restated). There are absolute constants eta > 0, c_1 > 0,
and an integer n_0 >= 3 such that, for every integer n >= n_0,
Delta(n) >= c_1 * n^(-2 + eta).
In particular, for every epsilon < eta, the bound Delta(n) <= C_epsilon *
n^(-2 + epsilon) fails for all sufficiently large n. So the almost n^(-2)
formulation of the Heilbronn triangle problem is false.
The two-line summary in plainer language:
- Sample integer points in the unit square with two carefully chosen
arithmetic restrictions.
- The first restriction (finite-field norms modulo a prime power) makes
small nonzero determinants impossible when three labels are distinct.
- The second restriction (finite-field caps modulo a large prime) makes
short integer relations impossible when three labels can collide.
- Together, these restrictions make it very unlikely that a random
sampled triple forms a small triangle.
- Delete one point per small triangle; most points survive.
- The survivors form a set with minimum triangle area bounded below by
a small positive power of n beyond n^(-2).
The exponent eta is tiny (roughly 1/(10^187)), but positive.
End of document.