================================================================================
A POWER IMPROVEMENT IN THE HEILBRONN TRIANGLE LOWER BOUND
================================================================================
Main theorem. There are absolute constants eta > 0, c_1 > 0, and n_0 >= 3
such that for every integer n >= n_0,
Delta(n) >= c_1 * n^(-2 + eta),
where Delta(n) is the largest forced minimum triangle area among n points
in the unit square. Consequently the "almost n^(-2)" formulation of the
Heilbronn triangle problem is FALSE.
The exponent we produce is eta = 2/(45435 k + 16) for an explicit fixed
integer k. It is astronomically small but positive.
--------------------------------------------------------------------------------
HOW TO READ THIS DOCUMENT
--------------------------------------------------------------------------------
The proof has two ingredients.
1. Finite-field norms plus a base-B encoding constrain columns mod a
prime power h = B^k so that small nonzero determinants cannot occur
when the labels are distinct.
2. A finite-field cap at a second prime q ~ h^100 constrains the columns
mod q so that short integer relations cannot occur. This handles the
case (determinant zero, or repeated labels) that the first
ingredient leaves open.
Together, the two constraints make bad triples (largest determinant
bounded by tau ~ h/2) rare among randomly sampled columns. Deleting one
point per bad triple leaves a large set whose smallest triangle has area
>> n^(-2 + eta).
Sections 2-7 are the engine room. A reader willing to accept the main
probability estimate (Corollary 6.4) can skip directly to Section 8.
--------------------------------------------------------------------------------
NOTATION
--------------------------------------------------------------------------------
Area(PQR) area of triangle PQR
det(u,v,w) det of the 3x3 matrix with columns u, v, w
Delta(P) minimum of Area over triples of distinct points of P
Delta(n) max of Delta(P) over |P| = n, P in [0,1]^2
|x| Euclidean length of x; also cardinality of a set
[N] {0, 1, ..., N-1}
F_q finite field with q elements
R_h Z/hZ
det L covolume of lattice L in its real span
A << B |A| <= C*B for an absolute constant C
A >> B same as B << A
A = o(B) A/B -> 0 in the indicated limit
All constants are absolute unless they depend on the fixed construction
parameters. None depends on the growing prime r or on the sampled data.
================================================================================
SECTION 1. INTRODUCTION
================================================================================
1.1 The problem
For 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),
the minimum being taken over triples of DISTINCT points, so a collinear
triple gives Delta(P) = 0. For n >= 3, define
Delta(n) = max over P in [0,1]^2 with |P| = n of Delta(P).
Two sanity checks:
- The maximum defining Delta(n) exists. The minimum-area function is
continuous on the compact space of ordered n-tuples, and positive
for suitable points in general position on a parabola. A tuple that
repeats a point has minimum area 0, so the maximum is attained at a
tuple of distinct points.
- Delta(P) can be 0. A maximizing configuration is therefore in
general position.
This is Heilbronn's problem [Roth 1951]. The goal is the 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).
Points with rational coordinates from nonlinear functions of field
elements: the determinants are nonzero integers, so after scaling to
[0,1]^2 the smallest triangle has area >> n^(-2).
- Random sampling. Take n random points, delete one point from each
small triangle. The number of small triangles is manageable, so
after deletion >> n^(-2).
KPS [1982] improved this to Delta(n) >> (log n)/n^2, DISPROVING the
original conjecture. Their argument represents small-area triples of a
random point set as edges of a hypergraph, removes short cycles, and
extracts a large subset avoiding all of them. So the original conjecture
is dead. What remains is:
1.3 The almost n^(-2) formulation
Zakharov [2026] asks: is it true that, for every eps > 0, there is a
constant C_eps with
Delta(n) <= C_eps * n^(-2 + eps) for all n >= n_0(eps)? (1.1)
That is: Delta(n) is essentially n^(-2) up to n^eps. This is consistent
with the KPS lower bound, which is o(n^(-2+eps)).
Our main theorem DISPROVES (1.1).
Theorem 1.1. There are absolute constants eta > 0, c_1 > 0, and
n_0 >= 3 such that, for every integer n >= n_0,
Delta(n) >= c_1 * n^(-2 + eta). (1.2)
Consequently, for eps = eta/2, we have Delta(n) / n^(-2+eta/2) >=
c_1 n^(eta/2) -> infinity, which contradicts (1.1) at eps = eta/2.
The exponent we produce is eta = 2/(45435 k + 16) for an explicit fixed
integer k (Section 8). It is tiny but positive.
1.4 Upper-bound history
Roth 1951 Delta(n) = o(1/n)
Schmidt 1972 refinements
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))
Two prior preprints claim stronger lower bounds than ours. Ellmann v12
acknowledges an unproved local-uniformity assumption (p. 3) and uses it
in Theorem 4 (pp. 5-6). Agama v13 Theorem 4.1 (pp. 12-13) counts a center
together with boundary points, creating a collinear triple (two endpoints
of a diameter and their midpoint); omitting the center leaves the
every-triple estimate unproved. These objections concern the cited
arguments, not the possibility of their asserted bounds. Our argument is
self-contained.
1.5 The two congruence conditions
The proof works with INTEGER COLUMNS u = (u_1, u_2, u_3)^T satisfying
0 <= u_1, u_2 < N and N <= u_3 < 2N. Each column 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 whose projected points give a triangle of area
|det A| / (2 A_{31} A_{32} A_{33}). (1.3)
Since A_{3j} in [N, 2N), this is at least |det A| / (16 N^3). Keeping
the determinant large keeps the triangle area large.
The sampling scheme imposes TWO arithmetic restrictions.
Condition A (main modulus h = B^k). Give each column an independent
uniform label xi in F_{r^d}, with d fixed and odd (we take d = 41) and
r growing. The label determines the column mod h by a specific digit
construction using the field norm from F_{r^d} to F_r of a Vandermonde
determinant. If the three labels are pairwise distinct, det A mod h has
no integer representative in [-tau, tau], where tau ~ h/2. The
construction combines the finite-field parabola of Erdos with a base-B
carry-free encoding: one designated base-B digit isolates the norm, and
a carry bound forces the determinant residue to be large.
Condition B (auxiliary prime q ~ h^100). Condition A leaves open the
case where two labels coincide: three collinear points are collinear
regardless of their labels, so Condition A cannot exclude determinant
zero. Fix a "cap" S in F_q^3 (no three collinear points) supported in a
small box, and set V = G_q(a + S) for a random shift a and a random
G_q in GL_3(F_q). This gives a random set V mod q with no short integer
relations among its elements.
The two moduli h and q are coprime, so by the Chinese remainder theorem
each prescribed pair of residues (mod h, mod q) has exactly (N/(hq))^3
integer lifts in the sampling box.
Combined:
- Triples with distinct labels: det A cannot be small.
- Triples with repeated labels: the auxiliary cap rules out
determinant zero and severely restricts small nonzero determinants.
1.6 The determinant-zero case
For a determinant-zero matrix A, the columns are linearly dependent. A
primitive integer null vector x satisfies Ax = 0. Every row of A lies in
the plane lattice x^perp, and a lattice count bounds the number of such
A. Two subcases:
- Affinely independent residues mod q. Then Condition B excludes short
relations, so |x| > H/2. A large null vector forces few matrices.
- Repeated residue columns mod q. Then two columns of A are equal
mod q. This is a strong extra condition. Combined with a bounded-norm
constraint on x, the count is small.
1.7 Organization
Section 2: lattice estimates with a prescribed nonzero determinant.
Section 3: field norms and the main-modulus digit construction.
Section 4: residue orbits mod h and a conditional digit moment.
Section 5: the auxiliary cap and its inclusion probabilities.
Section 6: sampling and the probability of a bad triple.
Section 7: determinant-zero triples.
Section 8: deletion, scaling, and the main theorem.
Section 9: Bertrand's postulate.
Conventions:
- Lengths are Euclidean.
- A primitive integer vector has coordinates with gcd one.
- A << B: |A| <= C*B for an absolute constant C. Dependence on the
fixed parameter k is indicated by <<_k.
- det L: covolume of L in its real span.
- All logarithms are natural.
================================================================================
SECTION 2. LATTICE ESTIMATES
================================================================================
We count 3x3 integer matrices whose rows lie in a fixed lattice, whose row
norms are bounded, and whose determinant is a prescribed nonzero integer.
Theorem 2.5 (the "fixed nonzero determinant" bound) is the goal; the four
lemmas leading up to it are standard geometry of numbers.
2.1 Successive minima
For a Euclidean lattice L of positive rank s, the SUCCESSIVE MINIMA are
lambda_1 <= ... <= lambda_s, where v_1 is a shortest nonzero vector of L,
and v_i is a shortest vector of L outside span(v_1, ..., v_{i-1}).
Lemma 2.1 (successive lengths). For a lattice L of positive rank s,
det L <= lambda_1 * ... * 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.
Proof. The determinant of the lattice L_0 = Z v_1 + ... + Z v_s is a
positive integer multiple of det L, and at most prod_i |v_i| = prod lambda_i
by Hadamard's inequality. This gives the upper bound.
For the lower bound, choose orthonormal coordinates whose first j
directions span v_1, ..., v_j for every j. Let
Q = { (a_1, ..., a_s) : |a_i| < lambda_i / sqrt(s) for all i }.
If a nonzero lattice vector z in Q has last nonzero coordinate j, then
z is outside span(v_1, ..., v_{j-1}) and
|z| < sqrt(sum_{i<=j} (lambda_i/sqrt(s))^2) <= sqrt(j/s) lambda_j
<= lambda_j, contradicting the definition of lambda_j. So no nonzero
lattice vector lies in Q, and the translates of Q/2 by L are pairwise
disjoint. Their total volume vol(Q/2) = s^(-s/2) prod lambda_i is at
most det L. QED.
2.2 Plane lattices in a disk
Lemma 2.2. Let L be a rank-two Euclidean lattice with successive lengths
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 0
are multiples of a single vector and number at most 1 + 2R/lambda_1.
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 every point of that coset
inside the disk. The parallelograms for a fixed coset are disjoint and lie
in a disk of radius at most R + (lambda_1+lambda_2)/2 <= 3R. This coset
therefore 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. So the points of L in the
disk are exactly the multiples of v_1 of length at most R; there are at
most 1 + 2R/lambda_1. QED.
2.3 Covolume of an integral plane
Lemma 2.3. Let y in Z^3 be primitive (coordinates have gcd one). Then
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 some positive integer g, then
det(Lambda intersect y^perp) = I |y| / g.
Proof. Choose u in Lambda with y · u = g. The map v |-> (y · v)/g
takes Lambda onto Z and has kernel Lambda intersect y^perp, splitting
by the section 1 |-> u. So a basis of the kernel together with u is a
basis of Lambda. Since the height of u above y^perp is g/|y|,
det Lambda = det(kernel) * (g/|y|),
hence 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
Lemma 2.4. Let R_1 >= R_2 >= R_3 >= 1 and t in Z be nonzero. The number
of triples (u_1, u_2, u_3) in Z^3 with |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).
Proof. The columns u_2, u_3 are linearly independent (otherwise det = 0).
Let y be their primitive normal, signed so its first nonzero coordinate is
positive. Then u_2 x u_3 = a y for some nonzero integer a, so
|y| <= |u_2| |u_3| <= R_2 R_3. Let mu_1 <= mu_2 be the successive lengths
of L_y. The columns give mu_1 <= R_3 and mu_2 <= R_2.
Fix (u_2, u_3). The equation det(u_1, u_2, u_3) = t is equivalent to
u_1 · y = t/a, whose integral solutions are either empty or a translate of
L_y. By Lemma 2.2(a) and Lemma 2.3, at most C R_1^2 / |y| such u_1
satisfy |u_1| <= R_1 (the required hypothesis mu_2 <= R_2 <= R_1 holds).
Fix the normal y. The possible u_2 with |u_2| <= R_2 in L_y number at
most C R_2^2 / |y|, and the possible u_3 number at most C R_3^2 / |y|,
by Lemma 2.2(a).
Case mu_2 <= R_3. Then the u_3 count is at most C R_3^2 / |y|, so the total
contribution is
C (R_1 R_2 R_3)^2 * sum_{0 < |y| <= R_2 R_3} |y|^{-3}
<< (R_1 R_2 R_3)^2 log(2 R_2 R_3),
the last step by dyadic shell (a shell of radius Y has O(Y^3) integer
vectors and contributes O(1) to the sum).
Case mu_2 > R_3. Group normals y by dyadic parameters U, Z >= 1 with
U <= mu_1 < 2U and Z <= mu_2 < 2Z. Lemma 2.1 gives |y| = det(L_y)
comparable to UZ. The number of normals in such a group is O(U^4 Z^2):
choose a shortest nonzero vector z in L_y, of length in [U, 2U); there are
O(U^3) choices for z; then the possible normals lie in L_z at distance
< 4UZ from 0 with second successive length at most 4U, so number at most
C (UZ)^2 / |z| <= C UZ^2 by Lemma 2.2(a). For each such normal, all
eligible third columns lie on a single line, so Lemma 2.2(b) gives at most
1 + 2R_3/mu_1 <= C R_3/U choices (using U <= mu_1 <= R_3). Multiplying:
O(U^4 Z^2) * (R_1^2 / (UZ)) * (R_2^2 / (UZ)) * (R_3/U)
= O(R_1^2 R_2^2 R_3 U) <= O((R_1 R_2 R_3)^2).
Summing over O(log(2 R_3) log(2 R_2)) dyadic groups gives the claim. QED.
2.5 Prescribed nonzero determinant
Proposition 2.5 (fixed nonzero determinant). Let Lambda subset Z^3 be a
full-rank lattice of index I, let X >= 2, and suppose the third successive
length lambda_3 of Lambda satisfies lambda_3 <= X. For every nonzero
integer t, the number of 3x3 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 C is absolute.
Proof. Let V be the matrix with rows the successive shortest vectors
v_1, v_2, v_3 of Lambda, and let Lambda_0 = Z v_1 + Z v_2 + Z v_3. By
Lemma 2.1,
m := [Lambda : Lambda_0] = |det V| / I <= 3^(3/2).
Every u in Lambda has coordinates in (1/m) Z in this 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.
Define the map A |-> Q = m A V^{-1}. It is injective and takes 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 this is not an integer,
no such A exist; otherwise Q has nonzero integer determinant m^3 t / det(V).
The j-th column of Q has length at most R_j = C_0 X / lambda_j with C_0 an
absolute constant. These radii satisfy R_1 >= R_2 >= R_3 >= 1 (the
inequality R_3 >= 1 uses integrality of Lambda: lambda_3 >= 1). By
Lemma 2.1 again,
R_j <= C_0 X, R_1 R_2 R_3 <= C_0^3 X^3 / I.
Applying 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 X))^2.
Adjusting C' finishes the proof. QED.
================================================================================
SECTION 3. FIELD NORMS AND THE FIRST CONGRUENCE CONDITION
================================================================================
The goal of this section is a single estimate (Lemma 3.3): under a specific
digit construction modulo h = B^k, any three columns with distinct
finite-field labels have determinant with NO integer representative in
[-tau, tau]. This is the "Condition A" of the overview.
The trick is to encode a finite-field norm, which is nonzero for distinct
labels, as one designated coefficient of a base-B expansion of the
determinant. A carry bound then forces the determinant residue to be
large.
3.1 Fixed parameters
Fix, independently of r,
d = 41
M = C(4d-1, d) = C(163, 41)
T = C(M, 3)
k = T^2 + 1.
These are huge but fixed integers. All "<" constants in the construction
are absolute (or depend only on k, which is fixed).
The specific choice d = 41 is not optimal; any sufficiently large odd d
works. We fix it here for clarity.
3.2 The field K = F_{r^d}
Let r be an odd prime and K = F_{r^d} the splitting field of X^(r^d) - X
over F_r. We use only these facts; see [Lidl-Niederreiter 1994, Chapter 2]:
(F1) K is a field of dimension d over F_r.
(F2) The Frobenius map sigma(t) = t^r is an F_r-automorphism of K,
sigma^d = id, and the fixed field is exactly F_r.
(F3) For t in K, the product t sigma(t) ... sigma^(d-1)(t) is the field
norm Nm_(K/F_r)(t), which belongs to F_r and is nonzero iff t != 0.
(F4) Fix an F_r-basis beta_1, ..., beta_d of K. Every element of K has
a unique expression sum_nu a_nu beta_nu with a_nu in F_r.
3.3 The determinant function on K-groups
Introduce 3d variables, arranged as a 3-by-d block
X = (X_{i nu}) for 1 <= i <= 3 and 1 <= nu <= d.
For a block X, define a vector in K^3 by
Z(X) = (sum_nu beta_nu X_{1 nu}, sum_nu beta_nu X_{2 nu}, sum_nu beta_nu X_{3 nu})^T.
For three disjoint blocks X^(1), X^(2), X^(3), define
D(X^(1), X^(2), X^(3)) = det(Z(X^(1)), Z(X^(2)), Z(X^(3))) in K.
The definition is a POLYNOMIAL of degree 1 in each variable and total
degree d in EACH of the three groups X^(1), X^(2), X^(3) (each factor D
contains one Z(X^(j)) and three linear forms, but the coefficients are not
counted as variables).
Let sigma act on the polynomial ring K[X^(1), X^(2), X^(3)] by applying
Frobenius to coefficients and fixing variables. Define the NORM POLYNOMIAL
N(X^(1), X^(2), X^(3)) = prod_{j=0}^{d-1} sigma^j(D(X^(1), X^(2), X^(3))).
By (F2), sigma permutes the factors, so N is fixed by sigma; by (F2), its
coefficients lie in F_r. Thus N is a polynomial in F_r[X^(1), X^(2), X^(3)]
of total degree d in each group, carrying all the arithmetic of the field
norm.
At arguments in F_r^{3d}, D evaluates to det(Z, Z', Z'') in K, and N
evaluates to Nm_(K/F_r)(D) by (F3). This is the only property of N we
need.
3.4 N is alternating
Transposing two of the three groups changes the sign of D (each factor
sigma^j(D) changes sign). The product of d factors changes sign by
(-1)^d = -1 when d is odd. Similarly for any transposition of the three
groups. So N is ALTERNATING as a polynomial in the three groups.
3.5 N on three explicit labels
For xi in K, put z(xi) = (1, xi, xi^2)^T; let X(xi) be the unique
F_r^{3d}-vector with Z(X(xi)) = z(xi). Then
D(X(xi_1), X(xi_2), X(xi_3)) = det(z(xi_1), z(xi_2), z(xi_3))
= Vandermonde(xi_1, xi_2, xi_3) * constant,
where constant = det(beta matrix) in K^x and Vandermonde(xi_1, xi_2, xi_3)
= prod_{i<j}(xi_j - xi_i). Consequently
N(X(xi_1), X(xi_2), X(xi_3)) = Nm_(K/F_r)(Vandermonde * constant)
!= 0 iff the three labels are distinct.
The implication "three distinct labels -> N nonzero in F_r" is what we
will use in 3.8.
3.6 Decomposition into monomial determinants
Lemma 3.1 (decomposition). There exist homogeneous degree-d polynomials
f_{ia} in F_r[X] for 1 <= i <= 3 and 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} ). (3.1)
For each a, the three polynomials f_{1a}, f_{2a}, f_{3a} are obtained from
three DISTINCT degree-d monomials m_{p_a}, m_{q_a}, m_{s_a} by multiplying
the first by a scalar c_a in F_r (possibly zero): f_{1a} = c_a m_{p_a},
f_{2a} = m_{q_a}, f_{3a} = m_{s_a}.
Proof. List the degree-d monomials in 3d variables as m_1, ..., m_M with
M = C(4d-1, d), the parameter chosen in 3.1. Expand N in the products
m_p(X^(1)) m_q(X^(2)) m_s(X^(3)). If two of p, q, s coincide, the
coefficient equals its own negation under transposing the corresponding
groups (3.4), so it is zero (r is odd). 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 with the signs of the
six permutations, exactly as in the determinant
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 set
f_{1a} = c_{pqs} m_p, f_{2a} = m_q, f_{3a} = m_s.
No division by 3! is used, so the argument works also for r = 3. QED.
3.7 Designated positions
Lemma 3.2 (designated positions). For 0 <= a, a', a'' < T, define
i_a = a, j_a = T a, ell_a = T^2 - (T+1) a. (3.2)
Then i_a, j_a, ell_a all lie in {0, ..., k-1}, and
i_a + j_{a'} + ell_{a''} = k - 1 = T^2 iff a = a' = a''. (3.3)
Proof. The ranges are i_a in [0, T-1], j_a in [0, T^2 - T], ell_a in
[1, T^2]. All are in [0, T^2] = [0, k-1].
Forward direction: rewrite i_a + j_{a'} + ell_{a''} = T^2 as
a + T a' = (T+1) a''.
Reducing mod T gives a = a'' since 0 <= a, a'' < T. Substituting:
a + T a' = (T+1) a, so T a' = T a, hence a' = a.
Reverse direction: i_a + j_a + ell_a = a + T a + T^2 - (T+1) a = T^2 = k-1.
QED.
3.8 The base-B digit construction
Fix an odd prime r. Set L = r^10, and use Bertrand's postulate (Lemma 9.1)
to choose a prime B satisfying
100 k^2 L^3 < B <= 200 k^2 L^3. (3.4)
Set h = B^k, tau = floor(B^{k-1}/2).
For each (i, v) in {1,2,3} x {0, ..., k-1}, we will define a digit
c_{iv} in {1, ..., L} such that the column
c = (c_1, c_2, c_3)^T in R_h, c_i = sum_v c_{iv} B^v mod h,
has good arithmetic properties.
Sampling rule for one column. Choose a label xi uniformly from K.
Independently, for each (i, v), choose a digit c_{iv} uniformly from
{1, ..., L} subject to the following congruence modulo r:
- c_{iv} = f_{1a}(X(xi)) mod r if (i, v) = (1, i_a) is designated;
- c_{iv} = f_{2a}(X(xi)) mod r if (i, v) = (2, j_a) is designated;
- c_{iv} = f_{3a}(X(xi)) mod r if (i, v) = (3, ell_a) is designated;
- c_{iv} = 0 mod r otherwise.
Every residue class modulo r contains exactly L/r = r^9 digits in
{1, ..., L} (because r | L). Each of the 3k digits is independent.
Lowest digit. Since c_{i0} in {1, ..., L} and L < B, the lowest digit is
a unit mod B. So each c_i is a unit in R_h.
Different columns use independent labels and fresh digits, even when the
labels coincide.
3.9 The determinant obstruction
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 the labels are
pairwise distinct, then det C in R_h has no integer representative in
[-tau, tau].
Proof. Define the integer polynomial
F(Y) = det( sum_{v=0}^{k-1} c_{iv}^{(j)} Y^v )_{1 <= i, j <= 3}
= sum_{u=0}^{3(k-1)} gamma_u Y^u.
Coefficient bound. For fixed u, expanding the determinant over the six
permutations and over triples of digit positions with total u:
|gamma_u| <= A_0 := 6 k^2 L^3. (3.5)
(Fix the permutation and two of the three positions; the third is
determined; each digit is at most L = r^10, so each product is at most L^3
and there are at most k^2 position choices.)
Designated coefficient. The coefficient gamma_{k-1} of Y^(k-1) equals
gamma_{k-1} = sum_{v_1+v_2+v_3 = k-1} sum_{sigma} sign(sigma) prod_i c_{i, v_i}^{(sigma(i))}.
Modulo r, every digit is zero unless (i, v_i) is a designated position of
row i. By Lemma 3.2, the sum v_1+v_2+v_3 = k-1 then forces v_i = i_a etc.
with the SAME a for all i. Therefore, mod r,
gamma_{k-1} = sum_a sum_sigma sign(sigma) prod_i f_{ia}(X(xi_{sigma(i)}))
= sum_a det( f_{ia}(X(xi_j)) )_{1<=i,j<=3}
= N(X(xi_1), X(xi_2), X(xi_3)) (3.6)
by Lemma 3.1. By section 3.5 and the assumption that the labels are
pairwise distinct, N(X(xi_1), X(xi_2), X(xi_3)) is nonzero in F_r.
So gamma_{k-1} != 0 as an integer.
Bounding the residue. Define the integer
S_C = sum_{u=0}^{k-1} gamma_u B^u.
Because the coefficients gamma_u for u >= k are killed by B^k = h, S_C is
an integer representative of det C modulo h. We now show |S_C| > tau and
|S_C + m h| > tau for every nonzero integer m.
Upper bound on |S_C|. From (3.5):
|S_C| <= 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) < h/2, (3.7)
using B - 1 >= 100 k^2 L^3.
Lower bound on |S_C|. Bounding the sum excluding the top term:
|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<k-1} gamma_u B^u|
>= B^{k-1} - (3/50)(B^{k-1} - 1)
= (47 B^{k-1} + 3)/50 > tau. (3.8)
Other representatives. Every other representative of det C mod h has the
form S_C + m h for some nonzero integer m. Then
|S_C + m h| >= h - |S_C| > h - h/2 = h/2 > tau (3.9)
by (3.7). So ALL representatives of det C mod h have absolute value > tau,
and the interval [-tau, tau] contains none of them. QED.
3.10 Consequence for the special-linear orbit
Corollary 3.4. Let G in SL_3(R_h), and let A be an integer matrix with
A mod h = G C for a digit matrix C with pairwise distinct labels. If
|det A| <= tau, then at least two labels of C coincide.
Proof. Since det G = 1 in R_h, det(GC) = det C mod h. As |det A| <= tau
and A mod h = GC = C mod h up to det, det C mod h has a representative in
[-tau, tau], contradicting Lemma 3.3 when the labels are distinct. QED.
For three independent uniform labels in K, at most 3/r^d of the triples
have a repeated label (union bound over the three pairs). This is the
"cheap" saving that the digit obstruction gives us; the auxiliary cap
(section 5) will strengthen it.
================================================================================
SECTION 4. RESIDUE ORBITS AND THE CONDITIONAL DIGIT MOMENT
================================================================================
We analyze the digit matrix C modulo h = B^k. Modulo a prime power, C
diagonalizes to diag(1, D, E) with D = B^b <= E = B^e, via invertible
row and column operations. The two exponents b, e control (i) the lattice
of integer lifts whose rows lie in the row span of C, and (ii) the size of
the SL_3 orbit through C.
The small divisor D has BOUNDED EXPECTATION given fixed labels, uniformly
over label triples. This conditional-moment bound is what makes the "cheap"
saving 3/r^d of section 3 sharp enough for the sampling analysis.
Throughout this section, B is a prime, k >= 1, h = B^k, R_h = Z/hZ. A
matrix in M_3(R_h) is invertible iff its reduction mod B is invertible in
M_3(F_B). The "row span" of C over R_h is the R_h-submodule of R_h^3
spanned by its rows.
4.1 Diagonal form and the row lattice
Lemma 4.1 (diagonal form). Let C in M_3(R_h) have at least one unit entry.
There exist P, Q in GL_3(R_h) and integers 0 <= b <= e <= k such that
C = P diag(1, B^b, B^e) Q. (4.1)
Set D = B^b, E = B^e, I = DE (all in {1, ..., h}). Then
Lambda_C = { v in Z^3 : v mod h in the row span of C }
is a full lattice of index I in Z^3, and E Z^3 ⊆ Lambda_C. Moreover, for
1 <= j <= k, we have b >= j iff every 2x2 minor of C is 0 mod B^j.
Proof. Diagonalization. Move a unit entry of C to (1,1), scale it to 1,
and clear its row and column by invertible operations. In the remaining
2x2 block, if all entries are 0 mod h, set b = e = k. Otherwise, choose an
entry of least B-adic valuation b, move it to (2,2), and scale it to make
its value B^b. Every other entry of the block is divisible by B^b, so row
and column subtractions clear its row and column. The final entry (3,3)
is divisible by B^b; scale it to B^e with b <= e <= k (or leave it as 0
when e = k). This proves (4.1), including the singular cases.
2x2 minors. Invertible row and column operations preserve the ideal
generated by the 2x2 minors. For diag(1, D, E) that ideal is D R_h
(generated by the (2,3) minor up to sign). Its image mod B^j is zero iff
b >= j. So the condition "b >= j" is equivalent to "every 2x2 minor of C
is 0 mod B^j".
Index and containment. Write M for the row span of C in R_h^3. Left
multiplication by P preserves M; right multiplication by Q is an
automorphism of R_h^3. So we may assume C = diag(1, D, E). Then
M = R_h x D R_h x E R_h, |M| = h (h/D) (h/E) = h^3 / I.
The reduction map Z^3 -> R_h^3 identifies Z^3/Lambda_C with R_h^3/M, so
[Z^3 : Lambda_C] = |R_h^3| / |M| = I.
For containment, D | E (as integers, since b <= e), so the row span of
diag(1, D, E) contains E R_h^3. Right multiplication by Q preserves
E R_h^3 (Q has entries in R_h). Therefore E R_h^3 ⊆ M, hence E Z^3 ⊆
Lambda_C. QED.
4.2 The SL_3 orbit
Lemma 4.2 (SL_3 orbit bound). Under the notation of Lemma 4.1, define
O_C = { GC : G in SL_3(R_h) }.
There is an absolute constant c_0 > 0 with
|O_C| >= c_0 h^8 / (D^3 E^2). (4.2)
For a uniformly random G in SL_3(R_h), GC is uniform on O_C. Every matrix
in O_C has the same row span and determinant mod h as C.
Proof. Let H ⊆ GL_3(R_h) be the stabilizer of C under left multiplication.
Conjugation by the diagonalizing matrix P of (4.1) identifies H with the
stabilizer of diag(1, D, E).
Count H. Suppose M in GL_3(R_h) satisfies M diag(1, D, E) = diag(1, D, E).
Column 1 gives M (1, 0, 0)^T = (1, 0, 0)^T, so M's first column is
exactly (1, 0, 0)^T. Column 2: M (0, D, 0)^T = (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 in R_h (i.e. is a multiple of B^{k-b} = h/D). There are D such
multiples per entry, so at most D^3 choices for the second column. Column
3: similarly at most E^3 choices. Discarding the invertibility condition:
|H| <= D^3 E^3. (4.3)
Determinant image of H. For every unit u in R_h^× 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).
If e < k, the units u = 1 + t B^{k-e} for t = 0, ..., B^e - 1 are all
units mod h and there are exactly E of them. If e = k, the condition is
vacuous and there are phi(h) = (1 - B^{-1}) E such units. In either case,
|det H| / |R_h^×| >= E / h. (4.4)
Orbit-stabilizer. Let K = SL_3 ∩ H = ker(det : H -> R_h^×). Then
|K| = |H| / |det H|, and |SL_3| = |GL_3| / |R_h^×|. Therefore
|O_C| = |SL_3| / |K|
= (|GL_3| / |R_h^×|) / (|H| / |det H|)
= (|GL_3| / |H|) (|det H| / |R_h^×|).
Now |GL_3| = h^9 (1 - B^{-1})(1 - B^{-2})(1 - B^{-3}) >= (21/64) h^9
for B >= 2, so |GL_3| / |H| >= (21/64) h^9 / (D^3 E^3) by (4.3).
Multiplying (4.4):
|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. The uniformity claim is immediate from the group
action, and row span plus determinant are left-multiplication invariant
for G in SL_3. QED.
4.3 Conditional moment of D
Lemma 4.3 (conditional digit estimate). Let r, L be positive integers with
r >= 2, r | L, and L < B. Let Lambda be a label set, and for each lambda
in Lambda 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, D = B^b be as in Lemma 4.1, and put theta = B (r/L)^4. Then:
(a) For every 1 <= j <= k:
Pr(b >= j | lambda_1, lambda_2, lambda_3) <= (r/L)^{4j}. (4.5)
(b) If theta < 1, then
E[D | lambda_1, lambda_2, lambda_3] <= 1/(1 - theta). (4.6)
Proof. Fix j in {1, ..., k}. Condition additionally on the first column
of C, and on the first entries of columns 2 and 3 (i.e. on C_{11}, C_{21},
C_{31}, C_{12}, C_{13}).
If b >= j, then Lemma 4.1 with the 2x2 minor condition gives, for (i, v)
in {2,3}^2,
C_{iv} = C_{i1} C_{11}^{-1} C_{1v} (mod B^j). (4.7)
The right side is entirely determined by the additional conditioning. So
if b >= j, each C_{iv} for (i, v) in {2,3}^2 is forced into a specific
residue class mod B^j, which fixes the first j base-B digits of C_{iv}
(i.e. d_{iv, 0}, ..., d_{iv, j-1}).
Each d_{ivu} takes L/r possible values, uniformly (residue class mod r).
So the probability that all four entries C_{22}, C_{23}, C_{32}, C_{33}
hit their prescribed digit values is at most (r/L)^{4j}. The four entries
use disjoint digit draws, even when the labels coincide. This proves (4.5).
Moment. Apply the pointwise identity
B^b = 1 + sum_{j=1}^k (B^j - B^{j-1}) 1_{b >= j}.
Taking expectations,
E[B^b | 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 last sum is at most 1/(1 - theta). QED.
4.4 Application to the digit construction
In the digit construction of 3.8, we take L = r^10 and B <= 200 k^2 L^3.
Then
theta = B (r/L)^4 = B r^4 / r^{40} = B / r^{36} <= 200 k^2 r^{-6}.
So theta <= 1/2 for all sufficiently large r, and (4.6) simplifies to
E[D | lambda_1, lambda_2, lambda_3] <= 2 (4.8)
for every fixed label triple (including repeated labels).
Corollary 4.4 (collision contribution). Suppose the three labels are
independent and uniform in a set of size r^d, and let F be the event that
at least two labels coincide. Then
E[D 1_F] <= 6 r^{-d}. (4.9)
Proof. Condition on the labels. By (4.8),
E[D 1_F | labels] <= 2 * 1_F.
Taking expectations and using Pr(F) <= 3/r^d (union bound over the three
pairs of labels) gives (4.9). QED.
This is the "cheap" saving the digit obstruction provides. Section 6
combines it with the auxiliary cap to gain a full power of N.
================================================================================
SECTION 5. THE AUXILIARY CAP
================================================================================
We construct a random set V in F_q^3 with two useful properties:
- No three distinct points of V are collinear (needed later for the
"affinely independent residues" case of section 7).
- Short integer relations among elements of V are impossible (needed
for the "repeated residues" case of section 7).
The construction: fix a cap S in a small box {(x, y, Q(x, y))} for a
quadratic form Q; then apply a random shift a and a random invertible map
G_q. The shift excludes short relations; the cap excludes collinear
triples.
5.1 Parameters
Let H = h^2 (so H > h). Choose a prime q with
h^100 < q <= 2 h^100, w = floor(q / (1000 H^2)). (5.1)
Bertrand's postulate (Lemma 9.1) supplies such a q for every sufficiently
large h; set from here on
q/(2000 H^2) <= w <= q/(1000 H^2), q >= 2000 H^2. (5.2)
We identify {0, 1, ..., w-1} with the corresponding elements of F_q.
5.2 The cap
Lemma 5.1 (Barlotti cap). For every prime q and every integer 1 <= w <= q,
there is a set S ⊆ {0, ..., w-1}^3 ⊆ F_q^3 with |S| >= w^3/q that
contains no three distinct collinear points.
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 }.
Q vanishes only at (0, 0). Take any line in F_q^3:
direction (v_1, v_2, v_3), point (x_0, y_0, z_0).
- If (v_1, v_2) != (0, 0), then membership in Gamma is a quadratic
equation in the line parameter, with leading coefficient Q(v_1,v_2)
!= 0. At most 2 solutions.
- If (v_1, v_2) = (0, 0) and v_3 != 0, membership is z_0 + t v_3 =
Q(x_0, y_0), a linear equation with one solution.
So Gamma, and hence every translate b + Gamma, contains no three distinct
collinear points.
For uniform b in F_q^3, each point of F_q^3 lies in b + Gamma with
probability |Gamma|/q^3 = 1/q. Hence
E_b |(b + Gamma) ∩ {0, ..., w-1}^3| = w^3/q.
Choose b attaining at least this average, and set S = (b + Gamma) ∩ box.
QED.
Fix such a set S and set s = |S|. From Lemma 5.1,
s >= q^2 / (2000^3 H^6). (5.3)
S is fixed BEFORE any further randomness.
5.3 Allowed shifts
For t in F_q, let ||t||_q denote the least absolute value of an integer
representative. Define the set of allowed shifts
A = { a in F_q^3 : ||m a_1||_q > 3 H w for all 1 <= m <= 3H }. (5.4)
Lemma 5.2 (allowed shifts exist in abundance). |A| >= q^3/2.
Proof. Fix m in {1, ..., 3H}. The set of a with ||m a_1||_q <= 3Hw is
excluded. Since 1 <= m <= 3H < q, the map t |-> m t is a bijection of F_q,
so the set of t in F_q with ||t||_q <= 3Hw has exactly 6Hw+1 elements
(the integers from -3Hw to 3Hw inclusive; note 3Hw < q/2 by (5.2), so
this set does not wrap around). Union bound over m in {1, ..., 3H}:
Pr_{a in F_q^3}(a not in A) <= 3H (6Hw+1) / q.
Since w <= q/(1000 H^2), we have 3H (6Hw+1) <= 3H * 6Hw + 3H
<= 18 H^2 w + 3H <= 18 q / 1000 + 3H. So
Pr(a not in A) <= 18/1000 + 3H/q <= 18/1000 + 3/2000 = 39/2000 < 1/2,
using 3H <= 3H * q/(2000 H^2) / ... = 3q/(2000 H) <= 3q/2000 (since
H >= 1). Therefore |A| >= q^3/2. QED.
5.4 Short-relation exclusion
Lemma 5.3. Let a be uniform on A, G_q uniform in GL_3(F_q), and
V = G_q(a + S). Then:
(a) |V| = s, 0 NOT in V, and V contains no three distinct collinear
points.
(b) Let x = (x_1, x_2, x_3) in Z^3 \ {0} with |x| <= H, and let u^(1),
u^(2), u^(3) be distinct elements of V. Then:
- 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 IMPOSSIBLE whenever the
three columns are affinely independent (in particular when they
are three distinct elements of V).
Proof. All properties are preserved under invertible affine maps, so
we work with T = a + S.
(a) Cardinality and 0 not in T. If a + v = 0 for some v in S, then
||a_1||_q = ||v_1||_q <= w-1 <= 3Hw, violating (5.4) at m = 1. So 0 is
not in T, and |T| = |S| = s. Translates of S inherit the cap property.
(b) Case m := x_1 + x_2 + x_3 != 0. Then 1 <= |m| <= 3H. Write u^(i) =
G_q(a + v^(i)) with v^(i) in S. Apply G_q^{-1} to the relation:
x_1(a + v^(1)) + x_2(a + v^(2)) + x_3(a + v^(3)) = 0 in F_q^3.
The left side equals m a + x_1 v^(1) + x_2 v^(2) + x_3 v^(3), so
m a = -(x_1 v^(1) + x_2 v^(2) + x_3 v^(3)).
Taking first coordinates:
m a_1 = -(x_1 v^(1)_1 + x_2 v^(2)_1 + x_3 v^(3)_1).
The right side is an integer of absolute value at most 3H(w-1) < 3Hw,
contradicting (5.4) at this m.
Case m = 0. Then x_3 = -x_1 - x_2, and the relation becomes
x_1 (u^(1) - u^(3)) + x_2 (u^(2) - u^(3)) = 0 in F_q^3.
Since x != 0 and |x| <= H < q, the triple x is nonzero in F_q^3, so at
least one of x_1, x_2 is nonzero mod q (using x_3 = -x_1-x_2 and x != 0).
If x_1 = 0 and x_2 != 0, then u^(2) = u^(3), contradicting distinctness;
similarly for x_2 = 0. If both x_1, x_2 are nonzero, then u^(1)-u^(3) and
u^(2)-u^(3) are linearly dependent over F_q, contradicting affine
independence of any three distinct points of V (which follows from the
cap property). QED.
5.5 The weight W and its three bounds
For any integer 3x3 matrix A, define
W(A) = (q^3/s)^3 * Pr( all three columns of A mod q lie in V ). (5.5)
The probability is over the random (a, G_q), with S fixed.
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, no column of A mod q is zero, and the columns are either
affinely independent or include two equal columns.
Proof. The restriction a in A (whose probability is >= 1/2 by Lemma 5.2)
at most doubles any probability when replaced by uniform a. So it suffices
to bound the version with UNIFORM a in F_q^3, then multiply by 2.
Affine independent case. The affine group AGL_3(F_q) acts transitively
on ordered affinely independent triples in F_q^3, of which there are
q^3(q^3-1)(q^3-q) ~ q^9. For any ordered affinely independent triple
(A_1, A_2, A_3) of columns, and any uniform affine map M in AGL_3(F_q),
the triple (M A_1, M A_2, M A_3) is uniform on these q^9 aff indep triples.
At most s(s-1)(s-2) <= s^3 of them lie in S^3. So
Pr(all three columns in V) <= 2 * s^3 / (q^3(q^3-1)(q^3-q)) << s^3 / q^9.
Multiplying by (q^3/s)^3 = q^9/s^3 gives W(A) << 1.
Rank >= 2 case. Suppose two of the columns, say A_1 and A_2, are linearly
independent mod q. For uniform G_q, the preimages G_q^{-1}(A_1) and
G_q^{-1}(A_2) form a uniform ordered pair of independent vectors in F_q^3,
at most s^2 of which lie in S^2 (there are (q^3-1)(q^3-q) independent
pairs total). So
Pr(A_1, A_2 mod q in V) <= 2 * s^2 / ((q^3-1)(q^3-q)) << s^2/q^6.
Requiring A_3 also in V only decreases this. Multiplying by (q^3/s)^3:
W(A) << (q^9/s^3) (s^2/q^6) = q^3/s.
General case. If some column of A mod q is zero, it cannot lie in V (V
contains no zero by Lemma 5.3(a)), so W(A) = 0. Otherwise fix a nonzero
column, say A_1. For uniform G_q, its preimage is uniform among the
q^3-1 nonzero vectors, of which at most s lie in S. So
Pr(A_1 mod q in V) <= 2 * s/(q^3-1) << s/q^3.
Multiplying by (q^3/s)^3: W(A) << q^9/s^3 * s/q^3 = (q^3/s)^2.
Support statement. If W(A) > 0, then all three columns of A mod q lie in V,
and 0 is not in V. The three elements are either affinely independent, or
two of them are equal (because three distinct collinear points are
excluded by the cap property). QED.
5.6 Normalization identity
Fix (a, G_q) independently of all labels, digits, and G_h. Given V, choose
the auxiliary residue of each sample independently and uniformly from V.
Since |V| = s for every outcome, for any prescribed ordered triple A mod q
of auxiliary residues,
Pr(all three auxiliary residues in V) / s^3 = W(A) / q^9. (5.6)
This identity is unchanged on conditioning on any main-modulus data, and
it is the normalization used in section 6 when the two congruences
combine by the Chinese remainder theorem.
================================================================================
SECTION 6. SAMPLING INTEGRAL COLUMNS
================================================================================
We now assemble a random distribution on integer columns in a box B,
combining the two arithmetic restrictions (mod h from section 3, mod q
from section 5) via the Chinese remainder theorem. The main result is a
bound on the probability that three sampled columns form a "bad" triple:
pairwise distinct projected points AND |det A| <= tau (Corollary 6.4).
6.1 The box and the sampling rule
Set
N = (h q)^10,
B = ( [0, N)^2 x [N, 2N) ) ∩ Z^3. (6.1)
For u in B, define its projection
pi(u) = (u_1/u_3, u_2/u_3) in [0, 1)^2.
Every u in B has 0 <= u_1, u_2 < N and N <= u_3 < 2N, so pi(u) is in the
unit square and u_3 is comparable to N. Since N = (h q)^10, h q divides N.
Choose G_h uniformly from SL_3(R_h), independently of V. Given (G_h, V),
sample columns u in B independently as follows.
(1) Draw a label xi uniform in K = F_{r^d} and its digit column c in
R_h^3 by the section 3.8 construction.
(2) Prescribe u mod h = G_h c.
(3) Independently choose u mod q uniformly from V.
(4) Among columns in B with those residues, choose u uniformly.
Since gcd(h, q) = 1 and h q | N, the CRT gives exactly (N/(h q))^3 integer
lifts per pair of residues, so (4) is well-defined for every outcome.
Notation for a triple of samples:
A = (u^(1), u^(2), u^(3)) integer 3x3 matrix with columns u^(j);
C = (c^(1), c^(2), c^(3)) digit matrix, elements of R_h;
xi_1, xi_2, xi_3 the labels.
Given C, apply Lemma 4.1 to define D, E with I = DE, the lattice
Lambda = Lambda_C, and the SL_3 orbit O_C = { GC : G in SL_3(R_h) }.
6.2 Proportional pairs
Lemma 6.1 (proportional pairs). For two sampled columns u, v,
Pr( pi(u) = pi(v) ) << (h q)^6 / N^3. (6.2)
Proof. Since u_3, v_3 > 0, pi(u) = pi(v) iff u and v are Q-proportional.
Every column in B is a positive integer multiple t z of a unique primitive
z in Z^3 with z_3 > 0; the multiplier satisfies t <= sqrt(6) N / |z|. So
the number of multiples of z in B is at most sqrt(6) N / |z|.
The number of ordered proportional pairs in B^2 (including u = v) is at
most
sum_{0 < |z| <= sqrt(6) N} (sqrt(6) N / |z|)^2
<< N^2 * sum_{0 < |z| <= sqrt(6) N} |z|^{-2} << N^3,
the last step by dyadic shell (a shell of radius Y contains O(Y^3) integer
vectors and contributes O(Y) to the sum).
Condition on both columns' residues at both moduli, on G_h, and on V.
Their lifts in B are independent and uniform on exactly (N/(h q))^3
columns each. The proportional-pair count bounds that within any two such
lift sets. Dividing by (N/(h q))^6 = (N/(h q))^6 and averaging gives (6.2).
QED.
6.3 The exact lifting identity
Lemma 6.2. Condition on the three labels and on the digit matrix C. For
any set E ⊆ B^3 of integer matrices,
Pr(A in E | C, labels) = (h^9/(N^9 |O_C|)) sum_{A in E : A mod h in O_C} W(A). (6.3)
Here W(A) is the auxiliary weight from (5.5).
Proof. Given (C, labels), the matrix G_h C is uniform on O_C (because G_h
is uniform in SL_3). Given (a, G_q), the three auxiliary residues are
independent and uniform on V (which has s elements). Given both residues,
the CRT lift is uniform among (N/(h q))^3 positions per column.
For a specific A in B^3, we therefore have
Pr(A is sampled | C, labels, a, G_q)
= (1/|O_C|) 1_{A mod h in O_C} (1/s^3) 1_{A mod q in V^3} ((h q)/N)^9.
Averaging over (a, G_q) (which determine V) and using the definition of
W(A) (with Pr(A mod q in V^3) = W(A) s^3/q^9):
Pr(A is sampled | C, labels) = (h^9/(N^9 |O_C|)) W(A) 1_{A mod h in O_C}.
Summing over A in E gives (6.3). QED.
6.4 Bad triples
Call a triple of samples BAD if
pi(u^(1)), pi(u^(2)), pi(u^(3)) are pairwise distinct
and |det A| <= tau.
Recall tau = floor(B^{k-1}/2), so 2 tau < h. A bad triple with A mod h in
any specific orbit O_C has at most one possible determinant t in
[-tau, tau]. By Corollary 3.4, if the labels are pairwise distinct, 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 parameters D, E, I = DE, row lattice Lambda = Lambda_C, and
orbit O_C. For each integer t with |t| <= tau, let A_t be the set of
matrices A with
- columns in B;
- pairwise distinct projections;
- A mod h in O_C;
- det A = t.
Then
sum_{A in A_t} W(A) << (log(2 N))^2 * N^6 / I^2. (6.4)
Proof. Case t != 0. Since 0 < |t| <= tau < q, det(A mod q) != 0, so
A mod q has rank 3 and its columns are affinely independent. Proposition
5.4 gives W(A) << 1.
Every row of A lies in Lambda and has norm less than 4N. Since
E Z^3 ⊆ Lambda (Lemma 4.1) and D | E, the third successive length of
Lambda satisfies lambda_3(Lambda) <= E <= h < 4N. Proposition 2.5 with
X = 4N gives
#(A in A_t) << (log(8 N))^2 (4 N)^6 / I^2 << (log(2 N))^2 N^6 / I^2.
Multiplying by W(A) << 1 gives (6.4).
Case t = 0. The stronger Proposition 7.1 below gives
O(log(2 N) (N^6/I^2)) for all matrices with rows in Lambda and pairwise
distinct projections. The orbit restriction only reduces this set. QED.
Corollary 6.4 (bad-triple probability). Three sampled columns satisfy
Pr(bad triple) << (log(2 N))^2 * h / (N^3 r^d). (6.5)
Proof. Condition on (labels, C). Let F be the event that at least two of
the labels coincide; if F fails, the conditional probability is zero by
Corollary 3.4. If F holds, Lemma 6.2 and Proposition 6.3, summed over the
at most one feasible t, give
Pr(bad triple | C, labels) << (h^9/(N^9 |O_C|)) * (log N)^2 * N^6/I^2.
Using |O_C| >= c_0 h^8/(D^3 E^2) (Lemma 4.2) and I = DE:
Pr(bad triple | C, labels) << (log N)^2 * (h^9/N^9) * (D^3 E^2/h^8)
* (N^6/(D^2 E^2))
= (log N)^2 * h D / N^3.
Averaging over labels and using E[D 1_F] <= 6 r^{-d} (Corollary 4.4):
Pr(bad triple) << (log N)^2 * (h/N^3) * E[D 1_F]
<< (log N)^2 * h / (N^3 r^d). (6.6)
This is (6.5). QED.
================================================================================
SECTION 7. DETERMINANT-ZERO TRIPLES
================================================================================
Goal: the t = 0 case of Proposition 6.3, i.e., the contribution of
determinant-zero matrices. This is the delicate case, because Condition A
is silent on det = 0 (three collinear points are collinear regardless of
their labels); Condition B is what breaks the tie.
Idea: for det A = 0, use a primitive integer null vector x of A. Every row
of A then lies in the plane lattice Lambda_C ∩ x^perp. Sum over x in
dyadic shells.
7.1 Setup and statement
Keep the 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) ∩ Z^3, and W(A) from (5.5).
Keep the digit matrix C fixed. Its parameters D, E, I = D E, lattice
Lambda = Lambda_C (index I in Z^3, contains E Z^3), and orbit O_C (size
>= c_0 h^8/(D^3 E^2)) are as in Lemma 4.1 and Lemma 4.2.
Proposition 7.1 (weighted zero count). Let Z be the set of integer 3x3
matrices A with
- columns in B,
- rows in Lambda,
- det A = 0,
- pairwise distinct projected columns.
Then
sum_{A in Z} W(A) << log(2 N) * N^6 / I^2. (7.1)
7.2 The plane lattice from a null vector
Lemma 7.2 (plane lattice). Let x in Z^3 be primitive. Define
Lambda_x = Lambda ∩ x^perp (a full lattice in x^perp),
g(x): x · Lambda = g(x) Z (an integer >= 1),
J_x = det(Lambda_x) (covolume in x^perp).
Then:
(a) g(x) | E; J_x = I |x| / g(x); g(x)^3 / I <= h^2.
(b) Lambda_x reduces onto Pi_x := {v in F_q^3 : v · x_bar = 0},
where x_bar = x mod q != 0.
(c) If Gamma ⊆ Lambda_x is a sublattice of index m, the number of
ordered triples (v_1, v_2, v_3) in Gamma with |v_i| <= 4N and
rational rank two is at most
C N^6 / (m J_x)^3.
Proof of (a). Since E Z^3 ⊆ Lambda (Lemma 4.1), we have x · (E Z^3) = E Z,
so g(x) | E and hence g(x) <= E <= h. Lemma 2.3 applied to Lambda gives
J_x = I |x| / g(x). Finally, g(x)^3 / I <= E^3/I = E^3/(DE) = E^2/D <= E^2
<= h^2 (since D >= 1). QED.
Proof of (b). Since x is primitive, x_bar != 0 in F_q^3, so its
coordinate in some direction is a nonzero residue.
Take any v_bar in Pi_x, i.e. x · v_bar ≡ 0 mod q. Choose an integer lift
v_0 with x · v_0 = q a_0 (this is an integer because x · v_0 ≡ 0 mod q).
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 = 0 exactly, and v ≡ v_0 mod q, so v is
an integer lift of v_bar in Z^3 ∩ x^perp.
Thus Z^3 ∩ x^perp reduces onto Pi_x. Then Lambda_x = Lambda ∩ x^perp
contains E (Z^3 ∩ x^perp), so under mod-q reduction it contains E Pi_x =
Pi_x (q | E is false because q > h >= E). Therefore Lambda_x mod q =
Pi_x.
Proof of (c). Suppose v_1, v_2, v_3 in Gamma, each of norm at most 4N,
have rational rank two. Then some pair, say v_1, v_2, is linearly
independent over Q. Since both are in Gamma with norm at most 4N, the
second successive minimum of Gamma satisfies lambda_2(Gamma) <= 4N.
Lemma 2.2(a) with R = 4N bounds the number of vectors of Gamma in the
ball of radius 4N by C (4 N)^2 / det(Gamma). The three vectors v_1, v_2,
v_3 are chosen from this ball, so the number of rank-two triples is at
most (C (4N)^2/det Gamma)^3 = C' N^6/(det Gamma)^3.
Since Gamma is a sublattice of Lambda_x of index m, and both have rank two,
det(Gamma) = m J_x. Therefore the triple count is at most
C' N^6/(m J_x)^3. QED.
7.3 The moment sum
Lemma 7.3 (moment). For R >= h,
sum over primitive x in Z^3 with R <= |x| < 2R of g(x)^3
<< R^3 I. (7.2)
Proof. From Lemma 7.2(a), g(x) divides E = B^e, so g(x) = B^{a(x)} for
some 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 = (integer row span of an integral
lift of C) + h Z^3, and B^j | h. So x in Lambda mod B^j is the same
condition as C x ≡ 0 mod B^j.
Modulo B^j, the diagonal form C = diag(1, B^b, B^e) (up to SL_3(R_h) and
GL_3(R_h) conjugation) reduces the equation C x ≡ 0 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 puts 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.
Fraction of good residue classes: B^(-j - max(j-b, 0)).
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
<< rho^3 * B^(-j - max(j-b, 0)).
Apply dyadic shell (rho = 2R) and telescope with g(x)^3 = B^{3 a(x)} =
sum_{j=0}^{e} B^{3j} 1_{B^j | g(x)} up to a factor of B^3:
sum_{R <= |x| < 2R} g(x)^3
<< R^3 * sum_{j=0}^{e} B^{3j} B^(-j - max(j-b, 0))
= R^3 * sum_{j=0}^{e} B^(2j - max(j-b, 0)).
Split the sum at j = b:
- For 0 <= j <= b: the exponent is 2j, contributing at most 2 B^{2b} = 2 D^2.
- For b < j <= e: the exponent is j + b, contributing at most 2 B^{e+b} = 2 E D = 2 I.
Both terms are at most 2 I (since D <= E, D^2 <= D E = I). So the whole
sum is at most 4 I, and
sum over primitive x with R <= |x| < 2R of g(x)^3 << R^3 I.
This proves (7.2). QED.
7.4 Proof of Proposition 7.1
Let A in Z. Its columns are nonzero (since each u^(j) has u_3 > 0), and
no two are proportional (their projections are distinct). So A has
rational rank two. Its nullspace has a primitive integer generator x,
unique up to sign. Every coordinate of x is nonzero: if x_1 = 0 then the
first column of A is 0, contradicting non-vanishing; if exactly one
coordinate of x is nonzero, A has only one nonzero column, contradicting
rank two. Finally, |x| <= |row_i(A)| |row_j(A)| <= (4N)(4N) = 16 N^2 for
any pair of independent rows.
Partition primitive x by dyadic shells R <= |x| < 2R for R = 1, 2, 4, ....
There are O(log(2 N)) shells. We will show that the weighted contribution
of one shell is O(N^6/I^2); summing over shells gives (7.1).
Fix a shell R. For one such primitive x, every row v of A lies in
Lambda_x = Lambda ∩ x^perp (since Ax = 0 implies v · x = 0 for each row).
The three rows span a 2-dim subspace of x^perp (since A has rank two).
By Lemma 7.2(c) with Gamma = Lambda_x (m = 1), the number of row triples
is at most
N^6 g(x)^3/(I^3 R^3). (7.3)
Any further constraint on A mod q gives a sublattice of index m > 1 and
multiplies the count by m^{-3}.
The weight W(A) depends on the mod-q structure. Three cases cover the
support of W (Proposition 5.4); we treat each.
CASE A: columns of A mod q are affinely independent.
By Lemma 5.3 (short-relation exclusion), the relation Ax = 0 in F_q^3
impossible unless |x| > H. Hence every contributing shell has R > H/2.
Proposition 5.4 gives W(A) << 1. Contribution per shell:
<< sum over x in shell of g(x)^3 * N^6/(I^3 R^3)
<< R^3 I * N^6/(I^3 R^3) (Lemma 7.3)
= N^6/I^2. (7.4)
CASE B: two columns of A mod q coincide.
Fix the pair, say i < j, and set delta = e_i - e_j. Then A delta ≡ 0
mod q, meaning v · delta ≡ 0 mod q for every row v of A.
Sub-case B1: x_bar NOT in F_q delta.
The 1-dim spaces F_q x_bar and F_q delta are distinct, so delta is not
in the annihilator F_q x_bar of Pi_x. Therefore the linear functional
v |-> v · delta does not vanish identically on Pi_x = {v : v · x_bar = 0},
and Pi_x ∩ delta^perp has codimension one in Pi_x (index q). Since
Lambda_x mod q = Pi_x (Lemma 7.2(b)), the sublattice
Gamma = {v in Lambda_x : v · delta ≡ 0 mod q}
has index q in Lambda_x. Also ker(A mod q) contains both x_bar and delta,
and x_bar NOT in F_q delta, so dim ker(A mod q) >= 2 and rank(A mod q) <= 1.
Thus W(A) << (q^3/s)^2 by Proposition 5.4. Contribution per shell:
<< sum over x of g(x)^3 * (q^3/s)^2 * N^6/(q^3 I^3 R^3)
<< R^3 I * (q^3/s)^2 * N^6/(q^3 I^3 R^3) (Lemma 7.3)
= N^6 q^3/(I^2 s^2).
Using s >= q^2/(2000^3 h^12), so s^2 >= q^4/(2000^6 h^24):
N^6 q^3/(I^2 s^2) <= N^6 (2000^6) h^24/(I^2 q) << N^6/I^2. (7.5)
Sub-case B2: x_bar in F_q delta, say x_bar = c delta with c in F_q^x.
The coordinate of x outside the pair i, j is divisible by q; since it is
a nonzero integer (all coords of x nonzero), it has absolute value >= q.
Thus |x| >= q, so a contributing shell has R > q/2.
Count of x's in such a shell. The nonzero multiples of delta give q-1
residue classes for x modulo q. Each residue class contains at most
C (2R/q + 1)^3 integer vectors of length less than 2R. So the number of
possible x in this shell is
<< (q - 1) (R/q + 1)^3 << R^3/q^2. (7.6)
Sub-case B2b: rank(A mod q) >= 2. Since two columns coincide mod q,
rank <= 2, so rank(A mod q) = 2. The kernel is exactly F_q delta (1-dim),
consistent with x_bar in F_q delta. Proposition 5.4 gives W(A) << q^3/s.
Also delta · v = 0 for every v in Pi_x (since x_bar in F_q delta means
delta is perpendicular to Pi_x), so no extra congruence from delta: m = 1.
Contribution per shell. For each fixed x, the count is at most
N^6 g(x)^3/(I^3 R^3). Using g(x)^3 <= I h^2 gives N^6 h^2/(I^2 R^3).
Summing over the R^3/q^2 possible x's in this shell gives N^6 h^2/(I^2 q^2).
Multiplying by W(A) << q^3/s gives N^6 h^2 q/(I^2 s).
Using s >= q^2/(2000^3 h^12):
N^6 h^14/(I^2 q) << N^6/I^2. (7.7)
Sub-case B2c: rank(A mod q) <= 1.
All rows of A mod q lie in one of the q+1 one-dimensional subspaces
of Pi_x. For each such line L, the preimage in Lambda_x has index q
(because |Pi_x / L| = q), so m = q and Proposition 5.4 gives
W(A) << (q^3/s)^2. Contribution per shell:
<< (R^3/q^2)(q+1) * N^6/(q^3 I^3 R^3) * I h^2 * (q^3/s)^2
= (q+1) N^6 h^2/(q^2 I^2) * (q^3/s)^2.
Using q+1 <= 2q and s^2 >= q^4/(2000^6 h^24):
<= 2 N^6 h^2/(q I^2) * q^6/s^2
= 2 N^6 h^2 q^5/(I^2 s^2)
<= 2 N^6 h^2 q^5 * 2000^6 h^24/(I^2 q^4)
= 2 * 2000^6 N^6 h^26/(I^2 q) << N^6/I^2. (7.8)
The four cases A, B1, B2b, B2c cover all A in Z (via Proposition 5.4,
whose support requires affinely independent columns or two equal columns).
Each shell contributes O(N^6/I^2), and there are O(log(2 N)) shells.
Therefore
sum_{A in Z} W(A) << log(2 N) * N^6/I^2.
This is (7.1). QED.
================================================================================
SECTION 8. DELETION, SCALING, AND THE MAIN THEOREM
================================================================================
Now we choose N large, sample 2 n_r columns, and delete one point per bad
event. Most samples survive, and the survivors have every triangle area
>= tau/(16 N^3).
8.1 Sample size and bad events
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) ∩ Z^3,
S fixed in {0, ..., w-1}^3, s = |S|.
Fix r a sufficiently large prime. Set
a_r = r sqrt(N^3/tau), n_r = floor(a_r). (8.1)
Since k >= 1 and B is an odd prime, tau >= 1 and n_r -> infinity.
Sample 2 n_r columns by the section 6 rule, with shared (G_h, V) and
independent conditional draws.
Define the random variable Z as
Z = #{ unordered pairs {u^(i), u^(j)} of samples with
pi(u^(i)) = pi(u^(j)) }
+ #{ unordered triples with pairwise distinct projections and
|det A| <= tau }.
8.2 Expectation of Z
Lemma 8.1. 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)
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).
For large n_r, C(2 n_r, 2) <= 2 n_r^2 and C(2 n_r, 3) <= (4/3) n_r^3. By
Lemma 6.1 and Corollary 6.4:
Pr(pi(u) = pi(v)) << (h q)^6/N^3,
Pr(bad triple) << (log(2 N))^2 h/(N^3 r^d).
Therefore
E[Z] << n_r^2 (h q)^6/N^3 + n_r^3 (log(2 N))^2 h/(N^3 r^d).
Dividing by n_r gives (8.2). QED.
8.3 Both terms in (8.2) tend to zero
Lemma 8.2. Both terms in (8.2) tend to zero as r -> infinity.
Proof. Term 1. From n_r <= a_r = r sqrt(N^3/tau) and N^{3/2} = (h q)^{15}
(recall N = (h q)^10):
n_r (h q)^6/N^3 <= r tau^{-1/2} (h q)^6 / (h q)^{15} = r tau^{-1/2} (h q)^{-9}.
Since tau >= 1 and h q >= h >= B^2 grows polynomially in r, term 1 -> 0.
Term 2. From n_r^2 <= r^2 N^3/tau:
n_r^2 (log(2 N))^2 h/(N^3 r^d) <= (log(2 N))^2 (h/tau) r^{-(d-2)}.
Since B^{k-1} >= 3 (as B >= 100), tau >= B^{k-1}/3, so
h/tau <= 3 h/B^{k-1} = 3 B.
Since B <= 200 k^2 r^30:
Term 2 <= 600 k^2 (log(2 N))^2 r^{30 - (d-2)} = 600 k^2 (log(2 N))^2 r^{-9},
because d = 41 gives 30 - 39 = -9. Therefore term 2 -> 0. QED.
Combining: E[Z] = o(n_r). Hence there is a sampled outcome with Z < n_r.
8.4 Deletion
Since E[Z] = o(n_r), there is a sampled outcome with Z < n_r for all
sufficiently large r. Fix one. For each bad event (a proportional pair or
a bad triple with pairwise distinct projections and |det A| <= tau), mark
one index in that event. At most Z indices are marked.
After deleting all marked indices, at least 2 n_r - Z > n_r samples
remain. Retain any n_r of them. Write P_r for the set of their projections
in [0, 1)^2. Then
- |P_r| = n_r;
- no two points of P_r share a projection (all such pairs had at
least one endpoint deleted);
- every triple of distinct points of P_r has pairwise distinct
projections and |det A| > tau.
The last fact is the key: every bad triple had at least one endpoint
deleted.
8.5 Area lower bound
A triangle with 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):
Area >= |det A| / (2 (2N)^3) = |det A| / (16 N^3).
Combined with |det A| > tau:
Delta(P_r) >= tau / (16 N^3). (8.3)
8.6 The exponent eta
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.3):
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. (8.4)
Now express n_r as a power of r. From the parameter choices,
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 in [B^{k-1}/3, B^{k-1}/2].
Up to absolute constants depending only on k,
B ~ r^30, h ~ r^{30k}, q ~ r^{3000k},
N ~ r^{30300k},
tau ~ r^{30(k-1)}.
Therefore
N^3/tau ~ r^{90900k - 30(k-1)} = r^{90870k + 30},
a_r = r sqrt(N^3/tau) ~ r^{45435k + 16},
n_r ~ r^{45435k + 16}.
Set alpha = 45435 k + 16. There are positive constants A_k < D_k depending
only on k with
A_k r^alpha <= n_r <= D_k r^alpha (8.5)
for every sufficiently large prime r.
8.7 Conversion to n^(-2+eta)
Since tau < h and N >= h^10, and n_r^2 Delta(P_r) >= r^2/64 (from (8.4)),
combine with (8.5). From n_r <= D_k r^alpha, so r >= D_k^{-1/alpha}
n_r^{1/alpha}, hence
r^2 >= D_k^{-2/alpha} n_r^{2/alpha}.
So
n_r^2 Delta(P_r) >= r^2/64 >= (1/64) D_k^{-2/alpha} n_r^{2/alpha}.
Divide by n_r^2:
Delta(P_r) >= c_* n_r^{-2 + 2/alpha}, c_* = (1/64) D_k^{-2/alpha} > 0.
Set
eta = 2/alpha = 2 / (45435 k + 16). (8.6)
Then for P_r,
Delta(P_r) >= c_* n_r^{-2 + eta}. (8.7)
8.8 Passing from the prime r to all n
Lemma 8.3. There are absolute constants c_1 > 0 and n_0 >= 3 with
Delta(n) >= c_1 n^{-2 + eta} for every integer n >= n_0.
Proof. Fix n large. Let m = ceil((n/A_k)^{1/alpha}). By Lemma 9.1
(Bertrand), there is a prime r with m < r <= 2m. Since m <= 2(n/A_k)^{1/alpha}
(for m >= 1, i.e., n sufficiently large) and A_k m^alpha >= n,
n <= A_k m^alpha <= A_k r^alpha <= n_r,
so n_r >= n. Also r <= 2m <= 2((n/A_k)^{1/alpha}+1) <= 4 (n/A_k)^{1/alpha}
for n sufficiently large, so
n_r <= D_k r^alpha <= D_k 4^alpha A_k^{-1} n = C_k n.
Fix any subset Q of P_r of size n. Removing points cannot decrease the
minimum triangle area, so Delta(Q) >= Delta(P_r). By (8.7),
Delta(Q) >= c_* n_r^{-2+eta} >= c_* C_k^{-2+eta} n^{-2+eta}.
Set c_1 = c_* C_k^{-2+eta} > 0. Then Delta(n) >= Delta(Q) >= c_1 n^{-2+eta}
for every sufficiently large n. QED.
8.9 Main theorem
Theorem 8.4. Let k, alpha = 45435 k + 16, eta = 2/alpha be as above.
There is an absolute c_1 > 0 such that, for every integer n large enough,
Delta(n) >= c_1 n^{-2 + eta}. (8.8)
Consequently the "almost n^(-2)" formulation of the Heilbronn triangle
problem is FALSE.
Proof. Immediate from Lemma 8.3. The constants depend only on k, which
is a fixed integer independent of r and n. QED.
================================================================================
SECTION 9. BERTRAND'S POSTULATE
================================================================================
Lemma 9.1 (Bertrand). For every integer m >= 2, there is a prime p with
m < p <= 2m.
Proof (Erdos 1932). Let n = m and suppose, for contradiction, that no
prime lies in (n, 2n].
Step 1. Binomial bound. The central binomial coefficient C(2n, n) is the
largest of the 2n+1 coefficients C(2n, j), whose sum is (1+1)^{2n} = 4^n.
So
C(2n, n) >= 4^n / (2n+1). (9.1)
Step 2. p-adic valuation. For a prime p,
v_p(C(2n, n)) = sum_{j >= 1} (floor(2n/p^j) - 2 floor(n/p^j)).
For any real x, floor(2x) - 2 floor(x) is 0 or 1, so each summand is 0 or
1 and the sum stops once p^j > 2n. Therefore
p^{v_p(C(2n, n))} <= 2n for every prime p. (9.2)
Step 3. Product of primes up to x. Let P(x) = product of primes p <= x.
An induction on x gives
P(x) <= 4^{x-1} <= 4^x for every integer x >= 1. (9.3)
Step 4. Splitting the binomial product. Write
C(2n, n) = product over primes p of p^{v_p(C(2n, n))}.
Split into three groups.
- Small primes p <= sqrt(2n). By (9.2), each such prime contributes at
most 2n; the group total is at most (2n)^{pi(sqrt(2n))} <=
(2n)^{sqrt(2n)}.
- Medium primes sqrt(2n) < p <= 2n/3. For such p, p^2 > 2n so only the
j=1 summand of v_p is nonzero; it is 0 or 1. So the group total is at
most the product of all primes p <= 2n/3, i.e., at most P(2n/3) <=
4^{2n/3}.
- Large primes 2n/3 < p <= 2n. For p in (2n/3, n], v_p(C(2n, n)) = 0
(floor(2n/p) = 2 and floor(n/p) = 1); for p in (n, 2n], v_p = 1 (the
case we assumed absent). So the group contributes 1.
Putting these together:
C(2n, n) <= (2n)^{sqrt(2n)} * 4^{2n/3}. (9.4)
Step 5. Contradiction. Combine (9.1) and (9.4):
4^n/(2n+1) <= (2n)^{sqrt(2n)} * 4^{2n/3}.
Taking log base 2:
n - log_2(2n+1) <= sqrt(2n) log_2(2n) + 2n/3,
equivalently
n/3 - log_2(2n+1) <= sqrt(2n) log_2(2n).
The left side grows like n/3, the right side like O(sqrt(n) log n), so this
fails for all large n. Contradiction.
Hence there is a prime in (n, 2n] for every sufficiently large n. The
remaining small n (2 <= n <= some N_0) are checked directly. QED.
================================================================================
END OF DOCUMENT
================================================================================
Main theorem. Delta(n) >= c_1 n^{-2+eta} for all sufficiently large n, with
eta = 2/(45435 k + 16) > 0 absolute. The "almost n^(-2)" formulation of the
Heilbronn triangle problem (Delta(n) <= C_eps n^{-2+eps} for all eps > 0)
is FALSE.