diff 54d2d91..3eba0e4 heilbronn_triangle_improvement_v2.txt
diff --git a/heilbronn_triangle_improvement_v2.txt b/heilbronn_triangle_improvement_v2.txt
index a7fec0c..17baded 100644
--- a/heilbronn_triangle_improvement_v2.txt
+++ b/heilbronn_triangle_improvement_v2.txt
@@ -2,2797 +2,1540 @@
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. There are absolute constants eta > 0, c_1 > 0, and n_0 >= 3
+such that for every integer n >= n_0,
---------------------------------------------------------------------------------
-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),
- 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.
-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.
+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
--------------------------------------------------------------------------------
- - Read section 0 (overview) and section 1 (introduction). These explain
- the problem, its history, and the shape of the proof.
+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.
- - Then read section 8 (deletion and scaling) and section 9 (the prime
- interval), the two finishing sections that assemble the main theorem.
+ 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.
- - Sections 2-7 are the engine room. Each begins with a short "what and
- why" paragraph.
+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).
-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.
+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 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).
+ 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 AND BACKGROUND
+SECTION 1. INTRODUCTION
================================================================================
-1.1 The problem statement
+1.1 The problem
-For any three points p, q, r in R^2, define
+For three points p, q, r in R^2, define
- Area(pqr) = (1/2) * |det(q - p, r - p)|.
+ 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).
+ Delta(P) = min over unordered triples {p, q, r} of P of Area(pqr),
-(A collinear triple has area zero.) For n >= 3, define
+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 facts:
+Two sanity checks:
- - 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.
+ - 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 zero: any three collinear points do the trick. A
- maximizing configuration must therefore be in general position.
+ - Delta(P) can be 0. A maximizing configuration is therefore in
+ general position.
-This is Heilbronn's problem. The goal is the exact growth rate of Delta(n).
+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):
+Heilbronn conjectured Delta(n) = O(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).
+Two elementary constructions attain 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).
+ - 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).
-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.
+ - 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).
-So the original conjecture is dead. What remains is the almost n^(-2)
-question.
+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) discusses the formulation:
+Zakharov [2026] asks: is it true that, for every eps > 0, there is a
+constant C_eps with
- 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).
+ Delta(n) <= C_eps * n^(-2 + eps) for all n >= n_0(eps)? (1.1)
-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)).
+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 this. We produce an absolute eta > 0 and a
-constant c_1 > 0 with
+Our main theorem DISPROVES (1.1).
- Delta(n) >= c_1 * n^(-2 + eta) for all sufficiently large n.
+Theorem 1.1. There are absolute constants eta > 0, c_1 > 0, and
+n_0 >= 3 such that, for every integer n >= n_0,
-Then, for epsilon = eta/2,
+ Delta(n) >= c_1 * n^(-2 + eta). (1.2)
- Delta(n) / n^(-2 + eta/2) >= c_1 n^(eta/2) -> infinity,
+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.
-so Delta(n) is NOT bounded by C n^(-2 + eta/2). This contradicts the almost
-n^(-2) formulation at epsilon = 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 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
+ 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.
- - 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.
+ - 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
================================================================================
-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.
+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 and their product
+2.1 Successive minima
-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}).
+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 every Euclidean lattice L of positive
-rank s,
- det L <= lambda_1 * lambda_2 * ... * lambda_s <= s^(s/2) * det L.
+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.
-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 = 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.
-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 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.
-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
+2.2 Plane lattices in a disk
- |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.
+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 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.
+ (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 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).
+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 (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
+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.
-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|.
+2.3 Covolume of an integral plane
-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
+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.
-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
+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
-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
-
+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).
-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 (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.
-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|
+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).
-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
+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).
- 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).
+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).
-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 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:
-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.
+ 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).
-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.
+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 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
-
+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.
-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
+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 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.
+ 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
================================================================================
-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.
+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 the following integers, all independent of r:
+Fix, independently of r,
d = 41
M = C(4d-1, d) = C(163, 41)
T = C(M, 3)
- k = T^2 + 1
+ 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).
-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.
+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}
-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:
+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 : 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.
+ (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})_{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).
+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
-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).
+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.
-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:
+3.5 N on three explicit labels
- 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.
+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
-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
+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'' (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:
+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.
- - 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.
+3.8 The base-B digit construction
- - Otherwise, require c_{iv} = 0 mod r.
+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).
-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.
+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.
-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}).
+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} 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).
+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.
-3.8 The determinant obstruction
+Different columns use independent labels and fresh digits, even when the
+labels coincide.
-We now prove the CENTRAL estimate: for distinct labels, det(c) has no
-small integer representative.
+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 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.
+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.
-THE DESIGNATED COEFFICIENT. Consider the coefficient gamma_{k-1} of
-Y^(k-1) in F(Y). Expanding F by rows takes the form
+================================================================================
+SECTION 4. RESIDUE ORBITS AND THE CONDITIONAL DIGIT MOMENT
+================================================================================
- 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))}.
+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.
-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:
+4.3 Conditional moment of D
- v_1 = i_a for some a, v_2 = j_{a'} for some a', v_3 = ell_{a''} for some a''.
+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.
-By Lemma 3.2, the sum v_1 + v_2 + v_3 = k - 1 then forces a = a' = a''. So
-modulo r,
+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).
- 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.
+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)
-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.
+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.
-BOUND THE DETERMINANT REPRESENTATIVE. Define the integer
+This is the "cheap" saving the digit obstruction provides. Section 6
+combines it with the auxiliary cap to gain a full power of N.
- S_C = sum_{u=0}^{k-1} gamma_u B^u.
+================================================================================
+SECTION 5. THE AUXILIARY CAP
+================================================================================
-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.
+We construct a random set V in F_q^3 with two useful properties:
-BOUND S_C IN ABSOLUTE VALUE. Using the coefficient bound,
+ - 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).
- |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.
+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.
-BOUND S_C AWAY FROM ZERO. Similarly, bounding the "sum which excludes the
-top term" gives
+5.1 Parameters
- |sum_{u=0}^{k-2} gamma_u B^u| <= A_0 * (B^(k-1) - 1) / (B - 1)
- <= (3/50) * (B^(k-1) - 1).
+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.
-Since gamma_{k-1} is a nonzero integer,
+5.2 The cap
- |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.
+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.
-Now, every OTHER representative of det C mod h is of the form
-S_C + m h for m in Z. For m != 0,
+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.
- |S_C + m h| >= h - |S_C| > h - h/2 = h/2 > tau.
+5.5 The weight W and its three bounds
-So ALL representatives of det C mod h have absolute value > tau. QED.
+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.
-3.9 Consequence for SL_3 orbits
+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.
-Lemma 3.3 has the following immediate corollary.
+================================================================================
+SECTION 6. SAMPLING INTEGRAL COLUMNS
+================================================================================
-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.
+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).
-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.
+6.1 The box and the sampling rule
-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.
+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.
-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.
+Choose G_h uniformly from SL_3(R_h), independently of V. Given (G_h, V),
+sample columns u in B independently as follows.
-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.
+ (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.
-================================================================================
-SECTION 4. RESIDUE ORBITS AND THE CONDITIONAL DIGIT MOMENT
-================================================================================
+ (2) Prescribe u mod h = G_h c.
-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:
+ (3) Independently choose u mod q uniformly from V.
- (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.
+ (4) Among columns in B with those residues, choose u uniformly.
- (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.
+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.
-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.
+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) }.
-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.
+6.2 Proportional pairs
-4.1 Diagonal form over R_h
+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.
-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
+6.3 The exact lifting identity
- C = P diag(1, B^b, B^e) Q.
+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).
-Set D = B^b, E = B^e, I = DE (all as positive integers). The subgroup
+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.
- Lambda_C = { v in Z^3 : v mod h is in the R_h row span of C }
+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.
-is a full-rank sublattice of Z^3 satisfying
+6.4 Bad triples
- [Z^3 : Lambda_C] = I, E Z^3 ⊆ Lambda_C.
+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.
-Moreover, for 1 <= j <= k, we have b >= j IF AND ONLY IF every 2x2
-minor of C vanishes modulo B^j.
+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.
-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.
+================================================================================
+SECTION 7. DETERMINANT-ZERO TRIPLES
+================================================================================
-Proof.
+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.
-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.
+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.
-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.
+7.1 Setup and statement
-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.
+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).
-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).
+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.
-For the diagonal matrix, M = R_h x D R_h x E R_h, which has size
+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)
- |M| = h * (h/D) * (h/E) = h^3 / I.
+7.2 The plane lattice from a null vector
-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.
+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.
-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:
+7.3 The moment sum
- E Z^3 ⊆ Lambda_C. QED.
+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)
-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.
+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.
-4.2 Size of the SL_3 orbit
+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.
-Lemma 4.2 (SL_3 orbit bound). Under the hypotheses of Lemma 4.1, define
- O_C = { GC : G in SL_3(R_h) }.
+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.
-There is an absolute constant c_0 > 0 such that
+Fraction of good residue classes: B^(-j - max(j-b, 0)).
- |O_C| >= c_0 * h^8 / (D^3 E^2).
+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)).
-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.
+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:
-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).
+ 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)).
-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.
+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.
-Write M for a stabilizer element, so M diag(1, D, E) = diag(1, D, E).
+7.4 Proof of Proposition 7.1
-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.
+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.
-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.
+================================================================================
+SECTION 8. DELETION, SCALING, AND THE MAIN THEOREM
+================================================================================
-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.
+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).
-Discarding the invertibility condition:
+8.1 Sample size and bad events
- |H| <= D^3 E^3. (4.1)
+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|.
-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):
+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.
- 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).
+Sample 2 n_r columns by the section 6 rule, with shared (G_h, V) and
+independent conditional draws.
-Count units with this property.
+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 }.
- - 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.
+8.2 Expectation of Z
- - If e = k: the condition is vacuous, so the count is
- phi(h) = B^k (1 - B^(-1)) = (1 - B^(-1)) E.
+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)
-In both cases:
+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.
- |det H| / |R_h^x| >= E / h. (4.2)
+8.5 Area lower bound
-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:
+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)
- |O_C| = |SL_3| / |K|
- = (|GL_3| / |R_h^x|) / (|H| / |det H|)
- = (|GL_3| / |H|) * (|det H| / |R_h^x|).
+8.6 The exponent eta
-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).
+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)
-Multiplying by (4.2):
+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)
- |O_C| >= (21/64) h^9 / (D^3 E^3) * (E / h)
- = (21/64) h^8 / (D^3 E^2).
+8.8 Passing from the prime r to all n
-So c_0 = 21/64 works. QED.
+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.
-4.3 Conditional moment of D
+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.
-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.
+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.
-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.
+8.9 Main theorem
-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
+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.
- { a in {1, ..., L} : a ≡ a_{iu}(lambda_j) (mod r) }.
+Proof. Immediate from Lemma 8.3. The constants depend only on k, which
+is a fixed integer independent of r and n. QED.
-Define C in M_3(R_h) by
+================================================================================
+SECTION 9. BERTRAND'S POSTULATE
+================================================================================
- C_{ij} = sum_{u=0}^{k-1} d_{iju} B^u (mod h).
+Lemma 9.1 (Bertrand). For every integer m >= 2, there is a prime p with
+ m < p <= 2m.
-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,
+Proof (Erdos 1932). Let n = m and suppose, for contradiction, that no
+prime lies in (n, 2n].
- 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.
+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.
================================================================================
-WHAT WE HAVE PROVEN
+END OF DOCUMENT
================================================================================
-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.
+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.