diff 3eba0e4..b283097 heilbronn_triangle_improvement_v2.txt
diff --git a/heilbronn_triangle_improvement_v2.txt b/heilbronn_triangle_improvement_v2.txt
index 17baded..94a2124 100644
--- a/heilbronn_triangle_improvement_v2.txt
+++ b/heilbronn_triangle_improvement_v2.txt
@@ -1,22 +1,15 @@
-================================================================================
-A POWER IMPROVEMENT IN THE HEILBRONN TRIANGLE LOWER BOUND
-================================================================================
-
-Main theorem. There are absolute constants eta > 0, c_1 > 0, and n_0 >= 3
-such that for every integer n >= n_0,
-
- Delta(n) >= c_1 * n^(-2 + eta),
-
-where Delta(n) is the largest forced minimum triangle area among n points
-in the unit square. Consequently the "almost n^(-2)" formulation of the
-Heilbronn triangle problem is FALSE.
-
-The exponent we produce is eta = 2/(45435 k + 16) for an explicit fixed
-integer k. It is astronomically small but positive.
-
---------------------------------------------------------------------------------
-HOW TO READ THIS DOCUMENT
---------------------------------------------------------------------------------
+For a finite set P in the plane, write Area(PQR) for the area of the
+triangle PQR, put Delta(P) for the minimum of Area(PQR) over triples of
+distinct points, and put Delta(n) for the supremum of Delta(P) over all
+n-point P contained in [0,1]^2.
+
+There are absolute constants eta > 0, c_1 > 0, and an integer n_0 >= 3
+with Delta(n) >= c_1 n^(-2 + eta) for every integer n >= n_0. The
+exponent is eta = 2/(45435 k + 16), k = C(C(163,41),3)^2 + 1; it is
+astronomically small but positive. The bound disproves the "almost
+n^(-2)" formulation of the problem, which would assert
+Delta(n) <= C_eps n^(-2 + eps) for every eps > 0 and every sufficiently
+large n.
The proof has two ingredients.
@@ -34,125 +27,89 @@ bounded by tau ~ h/2) rare among randomly sampled columns. Deleting one
point per bad triple leaves a large set whose smallest triangle has area
>> n^(-2 + eta).
-Sections 2-7 are the engine room. A reader willing to accept the main
-probability estimate (Corollary 6.4) can skip directly to Section 8.
-
---------------------------------------------------------------------------------
-NOTATION
---------------------------------------------------------------------------------
-
- Area(PQR) area of triangle PQR
- det(u,v,w) det of the 3x3 matrix with columns u, v, w
- Delta(P) minimum of Area over triples of distinct points of P
- Delta(n) max of Delta(P) over |P| = n, P in [0,1]^2
- |x| Euclidean length of x; also cardinality of a set
- [N] {0, 1, ..., N-1}
- F_q finite field with q elements
- R_h Z/hZ
- det L covolume of lattice L in its real span
- A << B |A| <= C*B for an absolute constant C
- A >> B same as B << A
- A = o(B) A/B -> 0 in the indicated limit
-
-All constants are absolute unless they depend on the fixed construction
-parameters. None depends on the growing prime r or on the sampled data.
-
-================================================================================
-SECTION 1. INTRODUCTION
-================================================================================
-
-1.1 The problem
+Conventions: F_q is the field with q elements; R_h = Z/hZ; det L is the
+covolume of a lattice L in its real span; |x| is Euclidean length; a
+primitive integer vector has gcd of coordinates 1; A << B means
+|A| <= C B for an absolute constant C. Constants may depend on the fixed
+integers k, d, B (defined during the construction) but never on the
+growing prime r or on the sampled data. All logarithms are natural.
-For three points p, q, r in R^2, define
+det(u,v,w) is the determinant of the 3x3 matrix with columns u, v, w;
+[N] = {0, 1, ..., N-1}; A = o(B) means A/B -> 0 in the indicated limit.
- Area(pqr) = (1/2) * |det(q-p, r-p)|.
+The maximum in the definition of 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, while a
+tuple that repeats a point has minimum area zero. A maximizing tuple
+therefore consists of distinct points; still Delta(P) can be zero, when
+three collinear points are present.
-For a finite set P in R^2 with |P| >= 3, define
+Roth (1951) proved Delta(n) = o(1/n) by a density increment argument,
+itself a precursor of his theorem on three-term progressions.
- Delta(P) = min over unordered triples {p, q, r} of P of Area(pqr),
+Roth 1951, https://londmathsoc.onlinelibrary.wiley.com/doi/pdf/10.1112/jlms/s1-26.3.198
-the minimum being taken over triples of DISTINCT points, so a collinear
-triple gives Delta(P) = 0. For n >= 3, define
+Two elementary constructions already give Delta(n) >> n^(-2):
- Delta(n) = max over P in [0,1]^2 with |P| = n of Delta(P).
+ - Erdos's finite-field parabola, recorded in the appendix of Roth 1951.
+ Each determinant of three columns is a nonzero integer, so after the
+ usual dilation to [0,1]^2 the smallest triangle has area >> n^(-2).
-Two sanity checks:
+ - Random sampling followed by deletion of one point per small triangle.
+ With O(n^2) small triangles in expectation and O(n) deletions
+ possible, the surviving set retains >> n 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.
+Komlos, Pintz and Szemeredi (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. The original conjecture is dead. What survives is the
+following weaker statement, formulated by Zakharov (2026): is it true
+that, for every eps > 0, there is a constant C_eps with
- - Delta(P) can be 0. A maximizing configuration is therefore in
- general position.
+Komlos, Pintz, Szemeredi 1982,
+https://londmathsoc.onlinelibrary.wiley.com/doi/pdf/10.1112/jlms/s2-25.1.159
-This is Heilbronn's problem [Roth 1951]. The goal is the growth rate of
-Delta(n).
-
-1.2 The original conjecture and its failure
-
-Heilbronn conjectured Delta(n) = O(n^(-2)).
-
-Two elementary constructions attain Delta(n) >> n^(-2):
-
- - Erdos's finite-field parabola (recorded in Roth 1951, Appendix).
- Points with rational coordinates from nonlinear functions of field
- elements: the determinants are nonzero integers, so after scaling to
- [0,1]^2 the smallest triangle has area >> n^(-2).
-
- - Random sampling. Take n random points, delete one point from each
- small triangle. The number of small triangles is manageable, so
- after deletion >> n^(-2).
-
-KPS [1982] improved this to Delta(n) >> (log n)/n^2, DISPROVING the
-original conjecture. Their argument represents small-area triples of a
-random point set as edges of a hypergraph, removes short cycles, and
-extracts a large subset avoiding all of them. So the original conjecture
-is dead. What remains is:
-
-1.3 The almost n^(-2) formulation
-
-Zakharov [2026] asks: is it true that, for every eps > 0, there is a
-constant C_eps with
+Zakharov 2026,
+https://londmathsoc.onlinelibrary.wiley.com/doi/pdf/10.1112/jlms.70447
Delta(n) <= C_eps * n^(-2 + eps) for all n >= n_0(eps)? (1.1)
That is: Delta(n) is essentially n^(-2) up to n^eps. This is consistent
with the KPS lower bound, which is o(n^(-2+eps)).
-Our main theorem DISPROVES (1.1).
+The theorem below disproves (1.1).
-Theorem 1.1. There are absolute constants eta > 0, c_1 > 0, and
+Theorem. There are absolute constants eta > 0, c_1 > 0, and
n_0 >= 3 such that, for every integer n >= n_0,
Delta(n) >= c_1 * n^(-2 + eta). (1.2)
-Consequently, for eps = eta/2, we have Delta(n) / n^(-2+eta/2) >=
-c_1 n^(eta/2) -> infinity, which contradicts (1.1) at eps = eta/2.
-
-The exponent we produce is eta = 2/(45435 k + 16) for an explicit fixed
-integer k (Section 8). It is tiny but positive.
-
-1.4 Upper-bound history
+Consequently, for eps = eta/2, Delta(n) / n^(-2+eta/2) >=
+c_1 n^(eta/2) -> infinity, which contradicts (1.1) at eps = eta/2. The
+exponent is eta = 2/(45435 k + 16) for an explicit fixed integer k. It
+is tiny but positive.
Roth 1951 Delta(n) = o(1/n)
- Schmidt 1972 refinements
- Roth 1972a, 1972b refinements
+ Schmidt 1972 refinements of Roth 1951
+ Roth 1972a, 1972b further 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.
+Cohen, Pohoata, Zakharov 2023, cpz2023.pdf, https://arxiv.org/pdf/2305.18253v1
+Cohen, Pohoata, Zakharov 2025, cpz2025.pdf, https://arxiv.org/pdf/2409.07658v2
-1.5 The two congruence conditions
+Two recent preprints assert stronger lower bounds. Ellmann (2025)
+declares in its abstract that the method is heuristic and gives in its
+Theorem 1 a construction with minimum triangle area at least
+c n0^(-3/2) (log n0)^2, slightly weaker than the n^(-4/3) shape sometimes
+attributed to it. Agama (2026) states an improved upper bound
+Delta(s) << s^(-2+eps) together with a corresponding improvement of the
+lower bound.
+
+Ellmann 2025, ellmann.pdf, https://arxiv.org/pdf/1703.03297v12
+Agama 2026, agama.pdf, https://arxiv.org/pdf/2006.05269v13
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
@@ -167,7 +124,7 @@ 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
+uniform label xi in F_{r^d}, with d fixed and odd (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
@@ -194,8 +151,6 @@ Combined:
- 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
@@ -208,42 +163,17 @@ A. Two subcases:
mod q. This is a strong extra condition. Combined with a bounded-norm
constraint on x, the count is small.
-1.7 Organization
-
- Section 2: lattice estimates with a prescribed nonzero determinant.
- Section 3: field norms and the main-modulus digit construction.
- Section 4: residue orbits mod h and a conditional digit moment.
- Section 5: the auxiliary cap and its inclusion probabilities.
- Section 6: sampling and the probability of a bad triple.
- Section 7: determinant-zero triples.
- Section 8: deletion, scaling, and the main theorem.
- Section 9: Bertrand's postulate.
-
-Conventions:
-
- - Lengths are Euclidean.
- - A primitive integer vector has coordinates with gcd one.
- - A << B: |A| <= C*B for an absolute constant C. Dependence on the
- fixed parameter k is indicated by <<_k.
- - det L: covolume of L in its real span.
- - All logarithms are natural.
-================================================================================
-SECTION 2. LATTICE ESTIMATES
-================================================================================
-
-We count 3x3 integer matrices whose rows lie in a fixed lattice, whose row
+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
+Proposition 5 (the "fixed nonzero determinant" bound) is the goal; the
+four lemmas leading up to it are standard geometry of numbers.
For a Euclidean lattice L of positive rank s, the SUCCESSIVE MINIMA are
lambda_1 <= ... <= lambda_s, where v_1 is a shortest nonzero vector of L,
and v_i is a shortest vector of L outside span(v_1, ..., v_{i-1}).
-Lemma 2.1 (successive lengths). For a lattice L of positive rank s,
+Lemma 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.
@@ -263,9 +193,13 @@ lattice vector lies in Q, and the translates of Q/2 by L are pairwise
disjoint. Their total volume vol(Q/2) = s^(-s/2) prod lambda_i is at
most det L. QED.
-2.2 Plane lattices in a disk
+The two-sided bound is Minkowski's second theorem (Minkowski 1896,
+Geometrie der Zahlen, Section 50); a modern treatment is Henk (2002),
+Theorem 1.3.
+
+Henk 2002, henk.pdf, https://arxiv.org/pdf/math/0204158v1
-Lemma 2.2. Let L be a rank-two Euclidean lattice with successive lengths
+Lemma 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
@@ -287,9 +221,7 @@ lambda_2 > R. The lattice on R v_1 is Z v_1. So the points of L in the
disk are exactly the multiples of v_1 of length at most R; there are at
most 1 + 2R/lambda_1. QED.
-2.3 Covolume of an integral plane
-
-Lemma 2.3. Let y in Z^3 be primitive (coordinates have gcd one). Then
+Lemma 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
@@ -297,15 +229,13 @@ of Z^3 of index I, and y · Lambda = gZ for some positive integer g, then
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
+by the splitting map 1 |-> u. So a basis of the kernel together with u is a
basis of Lambda. Since the height of u above y^perp is g/|y|,
det Lambda = det(kernel) * (g/|y|),
hence det(kernel) = I |y| / g. For Lambda = Z^3, primitivity gives
g = 1 (there is an integer u with y · u = 1). QED.
-2.4 Unequal column bounds
-
-Lemma 2.4. Let R_1 >= R_2 >= R_3 >= 1 and t in Z be nonzero. The number
+Lemma 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,
@@ -319,12 +249,12 @@ of L_y. The columns give mu_1 <= R_3 and mu_2 <= R_2.
Fix (u_2, u_3). The equation det(u_1, u_2, u_3) = t is equivalent to
u_1 · y = t/a, whose integral solutions are either empty or a translate of
-L_y. By Lemma 2.2(a) and Lemma 2.3, at most C R_1^2 / |y| such u_1
+L_y. By Lemma 2(a) and Lemma 3, at most C R_1^2 / |y| such u_1
satisfy |u_1| <= R_1 (the required hypothesis mu_2 <= R_2 <= R_1 holds).
Fix the normal y. The possible u_2 with |u_2| <= R_2 in L_y number at
most C R_2^2 / |y|, and the possible u_3 number at most C R_3^2 / |y|,
-by Lemma 2.2(a).
+by Lemma 2(a).
Case mu_2 <= R_3. Then the u_3 count is at most C R_3^2 / |y|, so the total
contribution is
@@ -334,13 +264,13 @@ the last step by dyadic shell (a shell of radius Y has O(Y^3) integer
vectors and contributes O(1) to the sum).
Case mu_2 > R_3. Group normals y by dyadic parameters U, Z >= 1 with
-U <= mu_1 < 2U and Z <= mu_2 < 2Z. Lemma 2.1 gives |y| = det(L_y)
+U <= mu_1 < 2U and Z <= mu_2 < 2Z. Lemma 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
+C (UZ)^2 / |z| <= C UZ^2 by Lemma 2(a). For each such normal, all
+eligible third columns lie on a single line, so Lemma 2(b) gives at most
1 + 2R_3/mu_1 <= C R_3/U choices (using U <= mu_1 <= R_3). Multiplying:
O(U^4 Z^2) * (R_1^2 / (UZ)) * (R_2^2 / (UZ)) * (R_3/U)
@@ -348,9 +278,7 @@ eligible third columns lie on a single line, so Lemma 2.2(b) gives at most
Summing over O(log(2 R_3) log(2 R_2)) dyadic groups gives the claim. QED.
-2.5 Prescribed nonzero determinant
-
-Proposition 2.5 (fixed nonzero determinant). Let Lambda subset Z^3 be a
+Proposition 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
@@ -360,7 +288,7 @@ The constant C is absolute.
Proof. Let V be the matrix with rows the successive shortest vectors
v_1, v_2, v_3 of Lambda, and let Lambda_0 = Z v_1 + Z v_2 + Z v_3. By
-Lemma 2.1,
+Lemma 1,
m := [Lambda : Lambda_0] = |det V| / I <= 3^(3/2).
Every u in Lambda has coordinates in (1/m) Z in this basis. If u = sum_j
alpha_j v_j and |u| <= X, Cramer's rule gives
@@ -374,17 +302,13 @@ 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,
+Lemma 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:
+Applying Lemma 4 to Q:
#(Q) <= C (R_1 R_2 R_3)^2 (log(2 R_1))^2 <= C' X^6 / I^2 (log(2 X))^2.
Adjusting C' finishes the proof. QED.
-================================================================================
-SECTION 3. FIELD NORMS AND THE FIRST CONGRUENCE CONDITION
-================================================================================
-
-The goal of this section is a single estimate (Lemma 3.3): under a specific
+The goal of this section is a single estimate (Lemma 8): 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.
@@ -394,8 +318,6 @@ labels, as one designated coefficient of a base-B expansion of the
determinant. A carry bound then forces the determinant residue to be
large.
-3.1 Fixed parameters
-
Fix, independently of r,
d = 41
M = C(4d-1, d) = C(163, 41)
@@ -405,12 +327,11 @@ These are huge but fixed integers. All "<" constants in the construction
are absolute (or depend only on k, which is fixed).
The specific choice d = 41 is not optimal; any sufficiently large odd d
-works. We fix it here for clarity.
-
-3.2 The field K = F_{r^d}
+works. It is fixed here for clarity.
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]:
+over F_r. Only these facts are used; see Lidl and Niederreiter (1994),
+Chapter 2:
(F1) K is a field of dimension d over F_r.
(F2) The Frobenius map sigma(t) = t^r is an F_r-automorphism of K,
@@ -420,7 +341,7 @@ over F_r. We use only these facts; see [Lidl-Niederreiter 1994, Chapter 2]:
(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
+Lidl and Niederreiter 1994, https://doi.org/10.1017/CBO9781139172769
Introduce 3d variables, arranged as a 3-by-d block
X = (X_{i nu}) for 1 <= i <= 3 and 1 <= nu <= d.
@@ -442,18 +363,14 @@ 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
+evaluates to Nm_(K/F_r)(D) by (F3). This is the only property of N
+needed.
Transposing two of the three groups changes the sign of D (each factor
sigma^j(D) changes sign). The product of d factors changes sign by
(-1)^d = -1 when d is odd. Similarly for any transposition of the three
groups. So N is ALTERNATING as a polynomial in the three groups.
-3.5 N on three explicit labels
-
For xi in K, put z(xi) = (1, xi, xi^2)^T; let X(xi) be the unique
F_r^{3d}-vector with Z(X(xi)) = z(xi). Then
D(X(xi_1), X(xi_2), X(xi_3)) = det(z(xi_1), z(xi_2), z(xi_3))
@@ -462,12 +379,10 @@ 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 implication "three distinct labels -> N nonzero in F_r" is what
+will be used below.
-Lemma 3.1 (decomposition). There exist homogeneous degree-d polynomials
+Lemma 6 (decomposition). There exist homogeneous degree-d polynomials
f_{ia} in F_r[X] for 1 <= i <= 3 and 0 <= a < T, such that
N(X^(1), X^(2), X^(3)) = sum_{a=0}^{T-1} det( (f_{ia}(X^(j)))_{1<=i,j<=3} ). (3.1)
For each a, the three polynomials f_{1a}, f_{2a}, f_{3a} are obtained from
@@ -490,9 +405,7 @@ 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
+Lemma 7 (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)
@@ -507,9 +420,7 @@ a + T a' = (T+1) a, so T a' = T a, hence a' = a.
Reverse direction: i_a + j_a + ell_a = a + T a + T^2 - (T+1) a = T^2 = k-1.
QED.
-3.8 The base-B digit construction
-
-Fix an odd prime r. Set L = r^10, and use Bertrand's postulate (Lemma 9.1)
+Fix an odd prime r. Set L = r^10, and use Bertrand's postulate (Lemma 29)
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).
@@ -535,9 +446,7 @@ a unit mod B. So each c_i is a unit in R_h.
Different columns use independent labels and fresh digits, even when the
labels coincide.
-3.9 The determinant obstruction
-
-Lemma 3.3 (determinant obstruction). Let C be a matrix of three columns
+Lemma 8 (determinant obstruction). Let C be a matrix of three columns
constructed as above, with labels xi_1, xi_2, xi_3. If the labels are
pairwise distinct, then det C in R_h has no integer representative in
[-tau, tau].
@@ -556,12 +465,12 @@ 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.
+row i. By Lemma 7, 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
+by Lemma 6. By the determinant function construction 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.
@@ -591,24 +500,18 @@ form S_C + m h for some nonzero integer m. Then
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
+Corollary 9. 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.
+[-tau, tau], contradicting Lemma 8 when the labels are distinct. QED.
For three independent uniform labels in K, at most 3/r^d of the triples
have a repeated label (union bound over the three pairs). This is the
"cheap" saving that the digit obstruction gives us; the auxiliary cap
-(section 5) will strengthen it.
-
-================================================================================
-SECTION 4. RESIDUE ORBITS AND THE CONDITIONAL DIGIT MOMENT
-================================================================================
+The auxiliary cap will strengthen it.
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
@@ -618,16 +521,14 @@ 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.
+saving 3/r^d of the digit obstruction 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.
+Lemma 10 (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
@@ -662,9 +563,15 @@ 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
+The diagonalization step is a Smith normal form computation over the
+local principal ideal ring R_h. The index I = DE is the product of the
+elementary divisors of C.
+
+Smith 1861, On Systems of Linear Indeterminate Equations and
+Congruences, Philosophical Transactions of the Royal Society of London
+151, 293-326.
-Lemma 4.2 (SL_3 orbit bound). Under the notation of Lemma 4.1, define
+Lemma 11 (SL_3 orbit bound). Under the notation of Lemma 10, 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)
@@ -706,9 +613,7 @@ So c_0 = 21/64 works. The uniformity claim is immediate from the group
action, and row span plus determinant are left-multiplication invariant
for G in SL_3. QED.
-4.3 Conditional moment of D
-
-Lemma 4.3 (conditional digit estimate). Let r, L be positive integers with
+Lemma 12 (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.
@@ -718,7 +623,7 @@ 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:
+Let b, D = B^b be as in Lemma 10, 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)
@@ -730,7 +635,7 @@ 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)
+If b >= j, then Lemma 10 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
@@ -751,16 +656,14 @@ Taking expectations,
= 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.
+In the digit construction, L = r^10 and B <= 200 k^2 L^3.
Then
theta = B (r/L)^4 = B r^4 / r^{40} = B / r^{36} <= 200 k^2 r^{-6}.
So theta <= 1/2 for all sufficiently large r, and (4.6) simplifies to
E[D | lambda_1, lambda_2, lambda_3] <= 2 (4.8)
for every fixed label triple (including repeated labels).
-Corollary 4.4 (collision contribution). Suppose the three labels are
+Corollary 13 (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)
@@ -770,37 +673,29 @@ Proof. Condition on the labels. By (4.8),
Taking expectations and using Pr(F) <= 3/r^d (union bound over the three
pairs of labels) gives (4.9). QED.
-This is the "cheap" saving the digit obstruction provides. Section 6
-combines it with the auxiliary cap to gain a full power of N.
-
-================================================================================
-SECTION 5. THE AUXILIARY CAP
-================================================================================
+This is the "cheap" saving the digit obstruction provides. The auxiliary cap
+combines it with the sampling rule to gain a full power of N.
We construct a random set V in F_q^3 with two useful properties:
- No three distinct points of V are collinear (needed later for the
- "affinely independent residues" case of section 7).
+ "affinely independent residues" case of the determinant-zero analysis).
- Short integer relations among elements of V are impossible (needed
- for the "repeated residues" case of section 7).
+ for the "repeated residues" case of the determinant-zero analysis).
The construction: fix a cap S in a small box {(x, y, Q(x, y))} for a
quadratic form Q; then apply a random shift a and a random invertible map
G_q. The shift excludes short relations; the cap excludes collinear
triples.
-5.1 Parameters
-
Let H = h^2 (so H > h). Choose a prime q with
h^100 < q <= 2 h^100, w = floor(q / (1000 H^2)). (5.1)
-Bertrand's postulate (Lemma 9.1) supplies such a q for every sufficiently
+Bertrand's postulate (Lemma 29) supplies such a q for every sufficiently
large h; set from here on
q/(2000 H^2) <= w <= q/(1000 H^2), q >= 2000 H^2. (5.2)
-We identify {0, 1, ..., w-1} with the corresponding elements of F_q.
-
-5.2 The cap
+Identify {0, 1, ..., w-1} with the corresponding elements of F_q.
-Lemma 5.1 (Barlotti cap). For every prime q and every integer 1 <= w <= q,
+Lemma 14 (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.
@@ -822,17 +717,23 @@ probability |Gamma|/q^3 = 1/q. Hence
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,
+This is the standard parabolic cap: a quadratic form in two variables
+that vanishes only at the origin parametrizes a conic, and any line meets
+a conic in at most two points. Large caps in PG(3, q) were classified by
+Barlotti (1956); the argument here is a special case.
+
+Barlotti 1956, Un'estensione del teorema di Segre-Kustaanheimo,
+Bollettino della Unione Matematica Italiana (3) 11, 96-98.
+
+Fix such a set S and set s = |S|. From Lemma 14,
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.
+Lemma 15 (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,
@@ -846,9 +747,7 @@ Since w <= q/(1000 H^2), we have 3H (6Hw+1) <= 3H * 6Hw + 3H
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
+Lemma 16. 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
@@ -890,20 +789,18 @@ u^(2)-u^(3) are linearly dependent over F_q, contradicting affine
independence of any three distinct points of V (which follows from the
cap property). QED.
-5.5 The weight W and its three bounds
-
For any integer 3x3 matrix A, define
W(A) = (q^3/s)^3 * Pr( all three columns of A mod q lie in V ). (5.5)
The probability is over the random (a, G_q), with S fixed.
-Proposition 5.4 (weight bounds). With absolute implied constants:
+Proposition 17 (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)
+Proof. The restriction a in A (whose probability is >= 1/2 by Lemma 15)
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.
@@ -926,7 +823,7 @@ 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
+contains no zero by Lemma 16(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.
@@ -937,28 +834,20 @@ 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
+it is the normalization used below when the two congruences
combine by the Chinese remainder theorem.
-================================================================================
-SECTION 6. SAMPLING INTEGRAL COLUMNS
-================================================================================
-
We now assemble a random distribution on integer columns in a box B,
-combining the two arithmetic restrictions (mod h from section 3, mod q
-from section 5) via the Chinese remainder theorem. The main result is a
+combining the two arithmetic restrictions (mod h from the digit construction, mod q
+from the auxiliary cap) via the Chinese remainder theorem. The main result is a
bound on the probability that three sampled columns form a "bad" triple:
-pairwise distinct projected points AND |det A| <= tau (Corollary 6.4).
-
-6.1 The box and the sampling rule
+pairwise distinct projected points AND |det A| <= tau (Corollary 21).
Set
N = (h q)^10,
@@ -972,7 +861,7 @@ Choose G_h uniformly from SL_3(R_h), independently of V. Given (G_h, V),
sample columns u in B independently as follows.
(1) Draw a label xi uniform in K = F_{r^d} and its digit column c in
- R_h^3 by the section 3.8 construction.
+ R_h^3 by the digit construction above.
(2) Prescribe u mod h = G_h c.
@@ -987,12 +876,10 @@ 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
+Given C, apply Lemma 10 to define D, E with I = DE, the lattice
Lambda = Lambda_C, and the SL_3 orbit O_C = { GC : G in SL_3(R_h) }.
-6.2 Proportional pairs
-
-Lemma 6.1 (proportional pairs). For two sampled columns u, v,
+Lemma 18 (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.
@@ -1013,9 +900,7 @@ columns each. The proportional-pair count bounds that within any two such
lift sets. Dividing by (N/(h q))^6 = (N/(h q))^6 and averaging gives (6.2).
QED.
-6.3 The exact lifting identity
-
-Lemma 6.2. Condition on the three labels and on the digit matrix C. For
+Lemma 19. 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).
@@ -1033,17 +918,15 @@ W(A) (with Pr(A mod q in V^3) = W(A) s^3/q^9):
Pr(A is sampled | C, labels) = (h^9/(N^9 |O_C|)) W(A) 1_{A mod h in O_C}.
Summing over A in E gives (6.3). QED.
-6.4 Bad triples
-
Call a triple of samples BAD if
pi(u^(1)), pi(u^(2)), pi(u^(3)) are pairwise distinct
and |det A| <= tau.
Recall tau = floor(B^{k-1}/2), so 2 tau < h. A bad triple with A mod h in
any specific orbit O_C has at most one possible determinant t in
-[-tau, tau]. By Corollary 3.4, if the labels are pairwise distinct, no
+[-tau, tau]. By Corollary 9, if the labels are pairwise distinct, no
such t exists; so a bad triple must have at least two labels equal.
-Proposition 6.3 (weighted count at a fixed determinant). Fix a digit
+Proposition 20 (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
@@ -1059,38 +942,34 @@ 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
+E Z^3 ⊆ Lambda (Lemma 10) and D | E, the third successive length of
+Lambda satisfies lambda_3(Lambda) <= E <= h < 4N. Proposition 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
+Case t = 0. The stronger Proposition 22 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
+Corollary 21 (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
+Corollary 9. If F holds, Lemma 19 and Proposition 20, 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:
+Using |O_C| >= c_0 h^8/(D^3 E^2) (Lemma 11) 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):
+Averaging over labels and using E[D 1_F] <= 6 r^{-d} (Corollary 13):
Pr(bad triple) << (log N)^2 * (h/N^3) * E[D 1_F]
<< (log N)^2 * h / (N^3 r^d). (6.6)
This is (6.5). QED.
-================================================================================
-SECTION 7. DETERMINANT-ZERO TRIPLES
-================================================================================
-
-Goal: the t = 0 case of Proposition 6.3, i.e., the contribution of
+Goal: the t = 0 case of Proposition 20, 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.
@@ -1099,17 +978,15 @@ Idea: for det A = 0, use a primitive integer null vector x of A. Every row
of A then lies in the plane lattice Lambda_C ∩ x^perp. Sum over x in
dyadic shells.
-7.1 Setup and statement
-
Keep the parameters from sections 3-6: h = B^k, H = h^2,
q prime with h^100 < q <= 2 h^100, w = floor(q/(1000 H^2)),
N = (h q)^10, B = [0,N)^2 x [N,2N) ∩ Z^3, and W(A) from (5.5).
Keep the digit matrix C fixed. Its parameters D, E, I = D E, lattice
Lambda = Lambda_C (index I in Z^3, contains E Z^3), and orbit O_C (size
->= c_0 h^8/(D^3 E^2)) are as in Lemma 4.1 and Lemma 4.2.
+>= c_0 h^8/(D^3 E^2)) are as in Lemma 10 and Lemma 11.
-Proposition 7.1 (weighted zero count). Let Z be the set of integer 3x3
+Proposition 22 (weighted zero count). Let Z be the set of integer 3x3
matrices A with
- columns in B,
- rows in Lambda,
@@ -1118,9 +995,7 @@ matrices A with
Then
sum_{A in Z} W(A) << log(2 N) * N^6 / I^2. (7.1)
-7.2 The plane lattice from a null vector
-
-Lemma 7.2 (plane lattice). Let x in Z^3 be primitive. Define
+Lemma 23 (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).
@@ -1133,8 +1008,8 @@ Then:
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
+Proof of (a). Since E Z^3 ⊆ Lambda (Lemma 10), we have x · (E Z^3) = E Z,
+so g(x) | E and hence g(x) <= E <= h. Lemma 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.
@@ -1157,7 +1032,7 @@ 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
+Lemma 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.
@@ -1166,13 +1041,11 @@ Since Gamma is a sublattice of Lambda_x of index m, and both have rank two,
det(Gamma) = m J_x. Therefore the triple count is at most
C' N^6/(m J_x)^3. QED.
-7.3 The moment sum
-
-Lemma 7.3 (moment). For R >= h,
+Lemma 24 (moment). For R >= h,
sum over primitive x in Z^3 with R <= |x| < 2R of g(x)^3
<< R^3 I. (7.2)
-Proof. From Lemma 7.2(a), g(x) divides E = B^e, so g(x) = B^{a(x)} for
+Proof. From Lemma 23(a), g(x) divides E = B^e, so g(x) = B^{a(x)} for
some integer 0 <= a(x) <= e.
Key observation. For 0 <= j <= e, the condition B^j | g(x) is equivalent
@@ -1210,8 +1083,6 @@ sum is at most 4 I, and
sum over primitive x with R <= |x| < 2R of g(x)^3 << R^3 I.
This proves (7.2). QED.
-7.4 Proof of Proposition 7.1
-
Let A in Z. Its columns are nonzero (since each u^(j) has u_3 > 0), and
no two are proportional (their projections are distinct). So A has
rational rank two. Its nullspace has a primitive integer generator x,
@@ -1228,21 +1099,21 @@ 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
+By Lemma 23(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.
+support of W (Proposition 17); 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
+By Lemma 16 (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:
+Proposition 17 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)
+ << R^3 I * N^6/(I^3 R^3) (Lemma 24)
= N^6/I^2. (7.4)
CASE B: two columns of A mod q coincide.
@@ -1254,13 +1125,13 @@ 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
+Lambda_x mod q = Pi_x (Lemma 23(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:
+Thus W(A) << (q^3/s)^2 by Proposition 17. 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)
+ << R^3 I * (q^3/s)^2 * N^6/(q^3 I^3 R^3) (Lemma 24)
= 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)
@@ -1278,7 +1149,7 @@ possible x in this shell is
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.
+consistent with x_bar in F_q delta. Proposition 17 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
@@ -1291,7 +1162,7 @@ Using s >= q^2/(2000^3 h^12):
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
+(because |Pi_x / L| = q), so m = q and Proposition 17 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.
@@ -1301,23 +1172,17 @@ Using q+1 <= 2q and s^2 >= q^4/(2000^6 h^24):
<= 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,
+The four cases A, B1, B2b, B2c cover all A in Z (via Proposition 17,
whose support requires affinely independent columns or two equal columns).
Each shell contributes O(N^6/I^2), and there are O(log(2 N)) shells.
Therefore
sum_{A in Z} W(A) << log(2 N) * N^6/I^2.
This is (7.1). QED.
-================================================================================
-SECTION 8. DELETION, SCALING, AND THE MAIN THEOREM
-================================================================================
-
Now we choose N large, sample 2 n_r columns, and delete one point per bad
event. Most samples survive, and the survivors have every triangle area
>= tau/(16 N^3).
-8.1 Sample size and bad events
-
Parameters from sections 3-7:
d = 41, M = C(163, 41), T = C(M, 3), k = T^2 + 1,
B a prime with 100 k^2 L^3 < B <= 200 k^2 L^3 (L = r^10),
@@ -1330,7 +1195,7 @@ Fix r a sufficiently large prime. Set
a_r = r sqrt(N^3/tau), n_r = floor(a_r). (8.1)
Since k >= 1 and B is an odd prime, tau >= 1 and n_r -> infinity.
-Sample 2 n_r columns by the section 6 rule, with shared (G_h, V) and
+Sample 2 n_r columns by the sampling rule above, with shared (G_h, V) and
independent conditional draws.
Define the random variable Z as
@@ -1339,25 +1204,21 @@ Define the random variable Z as
+ #{ unordered triples with pairwise distinct projections and
|det A| <= tau }.
-8.2 Expectation of Z
-
-Lemma 8.1. For every sufficiently large prime r,
+Lemma 25. For every sufficiently large prime r,
E[Z]/n_r << n_r (h q)^6 / N^3 + n_r^2 (log(2 N))^2 h/(N^3 r^d). (8.2)
Proof. By linearity of expectation,
E[Z] = C(2 n_r, 2) Pr(pi(u) = pi(v))
+ C(2 n_r, 3) Pr(bad triple).
For large n_r, C(2 n_r, 2) <= 2 n_r^2 and C(2 n_r, 3) <= (4/3) n_r^3. By
-Lemma 6.1 and Corollary 6.4:
+Lemma 18 and Corollary 21:
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.
+Lemma 26. 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):
@@ -1374,8 +1235,6 @@ 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
@@ -1392,8 +1251,6 @@ in [0, 1)^2. Then
The last fact is the key: every bad triple had at least one endpoint
deleted.
-8.5 Area lower bound
-
A triangle with columns u^(1), u^(2), u^(3) and matrix A has area
Area(pi(u^(1)), pi(u^(2)), pi(u^(3))) = |det A| / (2 A_31 A_32 A_33).
Since all columns have third coordinate A_{3j} in [N, 2N):
@@ -1401,8 +1258,6 @@ Since all columns have third coordinate A_{3j} in [N, 2N):
Combined with |det A| > tau:
Delta(P_r) >= tau / (16 N^3). (8.3)
-8.6 The exponent eta
-
Since tau < h and N >= h^10,
a_r = r sqrt(N^3/tau) > r sqrt(h^30/h) = r h^{29/2} -> infinity,
so n_r = floor(a_r) >= a_r/2 for sufficiently large r. Combined with (8.3):
@@ -1429,8 +1284,6 @@ 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
@@ -1444,12 +1297,10 @@ Set
Then for P_r,
Delta(P_r) >= c_* n_r^{-2 + eta}. (8.7)
-8.8 Passing from the prime r to all n
-
-Lemma 8.3. There are absolute constants c_1 > 0 and n_0 >= 3 with
+Lemma 27. There are absolute constants c_1 > 0 and n_0 >= 3 with
Delta(n) >= c_1 n^{-2 + eta} for every integer n >= n_0.
-Proof. Fix n large. Let m = ceil((n/A_k)^{1/alpha}). By Lemma 9.1
+Proof. Fix n large. Let m = ceil((n/A_k)^{1/alpha}). By Lemma 29
(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,
@@ -1463,22 +1314,16 @@ minimum triangle area, so Delta(Q) >= Delta(P_r). By (8.7),
Set c_1 = c_* C_k^{-2+eta} > 0. Then Delta(n) >= Delta(Q) >= c_1 n^{-2+eta}
for every sufficiently large n. QED.
-8.9 Main theorem
-
-Theorem 8.4. Let k, alpha = 45435 k + 16, eta = 2/alpha be as above.
+Theorem 28. Let k, alpha = 45435 k + 16, eta = 2/alpha be as above.
There is an absolute c_1 > 0 such that, for every integer n large enough,
Delta(n) >= c_1 n^{-2 + eta}. (8.8)
Consequently the "almost n^(-2)" formulation of the Heilbronn triangle
problem is FALSE.
-Proof. Immediate from Lemma 8.3. The constants depend only on k, which
+Proof. Immediate from Lemma 27. The constants depend only on k, which
is a fixed integer independent of r and n. QED.
-================================================================================
-SECTION 9. BERTRAND'S POSTULATE
-================================================================================
-
-Lemma 9.1 (Bertrand). For every integer m >= 2, there is a prime p with
+Lemma 29 (Bertrand). For every integer m >= 2, there is a prime p with
m < p <= 2m.
Proof (Erdos 1932). Let n = m and suppose, for contradiction, that no
@@ -1531,10 +1376,6 @@ fails for all large n. Contradiction.
Hence there is a prime in (n, 2n] for every sufficiently large n. The
remaining small n (2 <= n <= some N_0) are checked directly. QED.
-================================================================================
-END OF DOCUMENT
-================================================================================
-
Main theorem. Delta(n) >= c_1 n^{-2+eta} for all sufficiently large n, with
eta = 2/(45435 k + 16) > 0 absolute. The "almost n^(-2)" formulation of the
Heilbronn triangle problem (Delta(n) <= C_eps n^{-2+eps} for all eps > 0)