A composite modulus and Frobenius digits in the Heilbronn triangle construction

Introduction

For a finite set $P \subset[0,1]^2$ with $|P| \ge3$ let $\Delta(P)$ be the least area of a triangle with vertices in $P$, and let $\Delta(n)$ be the maximum of $\Delta(P)$ over $n$-point sets. Komlós, Pintz and Szemerédi proved $\Delta(n) \gg(\log n)/n^2$ [4]. OpenAI [1] proved a power improvement $\Delta(n) \ge c_1 n^{-2+\eta}$ with $\eta= 2/(45435k + 16)$, $k = T^2 + 1$, $T = \binom{M}{3}$, $M = \binom{163}{41}$, so that $\eta\approx10^{-235.5}$. Their construction samples integral columns whose residues modulo a main modulus $h$ carry a determinant obstruction coming from a field norm, together with an auxiliary cap modulo a second prime $q$, and deletes the few bad triples.

Public follow-up work reduced the parameters inside the same framework: Blinov [2] lowered the extension degree to $d = 5$ using row-dependent digit lengths, label tags, a fresh-digit collision bound and a slab version of the auxiliary cap, and the Euler team [3] obtained the claimed exponent $\eta= 2/100866719$ with $k = 408781$ and a smaller lift box.

The two new ingredients are the following.

Composite modulus. Let $r$ be the label prime and choose the digit base $B=rB_{2}$ with $B_{2}$ prime. The main modulus is $h=rB^{k-1}$. Since $B \equiv0$ modulo $r$, the part of the determinant above the digit position $k-1$ reduces modulo $r$ to the single designated coefficient, whose residue is the field norm. Distinct labels then exclude every representative of absolute value at most $\tau\approx B^{k-1}/2$, while $h/\tau\approx2r$ instead of $\approx2B$. The price of a label collision becomes $r^{2\gamma}\cdot r^{-d}$ and $d=3$ suffices (§ 6).

Frobenius digits. The norm of the Vandermonde product, $\mathrm{N}(V)=\prod_{t}V^{r^{t}}$, has monomials whose exponents have $r$-adic digits in $\{0,1,2\}$, with a coefficient that factors over the digits. We place the monomials in the digit positions by a mixed-radix convolution in which each lower Frobenius digit is handled by a fixed three-row design of radix $6$ (Table 1), the most significant digit by a design whose rows 1 and 3 never reach the target together (Table 2), and the descent to $F_{r}$ by a trace digit of radix $2d-1$ in a polynomial basis. With $d=3$ this uses $k=1440$ positions.

row	options $(x,u,\epsilon)$
1	$(0,1,+)$, $(0,3,+)$, $(1,4,-)$, $(2,0,+)$
2	$(0,1,+)$, $(1,2,+)$, $(2,0,-)$
3	$(0,3,-)$, $(0,1,+)$, $(1,4,+)$, $(2,0,+)$

row	options $(x,u,\epsilon)$
1	$(0,4,+)$, $(1,1,-)$, $(2,0,+)$
2	$(0,5,-)$, $(0,6,-)$, $(1,3,-)$, $(2,1,+)$
3	$(0,5,-)$, $(0,4,+)$, $(1,2,-)$, $(2,0,-)$

Everything else follows the framework of [1] with the row-dependent digit lengths and the slab cap of [2] and the smaller lift box of [3]. We give proofs of every statement that changes, citing [1] for the lattice-point counts and the weight bounds of the auxiliary cap, whose proofs apply with the changes indicated.

Conventions. $A \ll B$ means $|A| \le CB$ with $C$ depending only on the fixed parameters $d=3$ and $k=1440$, never on the growing prime $r$. Lengths are Euclidean. All logarithms are natural.

Frobenius digits

The digit design

For $(x,y,z) \in\{0,1,2\}^{3}$ let $w(x,y,z)$ be the sign of the permutation $0 \mapsto x$, $1 \mapsto y$, $2 \mapsto z$ when $\{x,y,z\}=\{0,1,2\}$, and $w(x,y,z)=0$ otherwise. Then, for commuting indeterminates,

A design is a triple of finite lists $\mathcal{O}_{1},\mathcal{O}_{2},\mathcal{O}_{3}$ of options; each option $o$ carries a value $x(o) \in\{0,1,2\}$, a height $u(o) \in\mathbb{Z}_{\ge0}$ and a sign $\epsilon(o) \in\{\pm1\}$. We use the design $\mathcal{D}_{6}$ of Table 1, with target $\kappa=5$.

Proof. A finite check of the $4 \cdot3 \cdot4=48$ option triples; see anc/check_design.py. For example, for $(x,y,z)=(0,1,2)$ the option triples have heights $(1,2,0)$ and $(3,2,0)$; only the second sums to $5$, with sign $+$. For $(0,0,0)$ the triples summing to $5$ are $(1,1,3)$ with sign $-$ and $(3,1,1)$ with sign $+$, which cancel.

For the most significant digit we use the design $T_7$ of Table 2, with target $7$.

Proof. A finite check; see anc/check_design.py. For (T1), the heights in rows 1 and 3 are $\{0,1,4\}$ and $\{0,2,4,5\}$, whose sums avoid 7.

Field, labels and the norm

Fix $d=3$. Let $r>6d$ be a prime, $\mathbb{F}=\mathbb{F}_r$, and $K=\mathbb{F}_{r^d}=\mathbb{F}[\theta]$ with $\theta$ a root of an irreducible cubic. Write $c_\mu(\xi)$, $\mu=0,1,2$, for the coordinates of $\xi\in K$ in the basis $1,\theta,\theta^2$, and $\operatorname{Tr}$ for the trace $K\to\mathbb{F}$. For $e=(e_0,e_1,e_2)\in\{0,1,2\}^3$ put $\xi^{[e]}=\xi^{e_0+e_1r+e_2r^2}=\prod_t(\xi^{r^t})^{e_t}$. For labels $\xi_1,\xi_2,\xi_3\in K^\times$ let $V=(\xi_2-\xi_1)(\xi_3-\xi_1)(\xi_3-\xi_2)$ and $N(V)=\prod_{t<d}V^{r^t}\in\mathbb{F}$. Since $d$ is odd, $N(-v)=-N(v)$, so $N(V)$ is alternating in the labels; it is nonzero when the labels are distinct.

Positions and residues

Use the mixed radix with digit weights

that is, a trace digit of radix $2d-1=5$, two Frobenius digits of radix 6 (digits $t=0,1$, design $D_6$) and a most significant Frobenius digit $(t=2$, design $T_7$). Write $\mathcal{O}^{(t)}_i$ for the options of row $i$ in the design of digit $t$. For a row $i$ and an option word $o=(o_0,o_1,o_2)$ with $o_t\in\mathcal{O}^{(t)}_i$ put

The terms of the three rows, their positions and their functions $K\to\mathbb{F}$ are:

Put

The largest position is $2+4\cdot5+4\cdot30+4\cdot180=862$ in row 1, $2+2\cdot5+2\cdot30+6\cdot180=1152$ in row 2 and $4+4\cdot5+4\cdot30+5\cdot180=1044$ in row 3, all below $k-1=1439$. For a label $\xi\in K^\times$, a row $i$ and a position $0\le v<k$, let $\rho_{i,v}(\xi)\in\mathbb{F}$ be the sum of the functions of all row-$i$ terms at position $v$ (zero if there are none), except that we add the control

by (T2) row 2 has no term at position 0. By (T2) and Lemma 2.2, the only terms at position 0 are, in row 1, the word of value $(2,2,2)$ with $\mu=0$, of function $c_0(\xi^{[2,2,2]})=c_0(N(\xi)^2)=N(\xi)^2$, and, in row 3, the word of value $(2,2,2)$ with $s=4$, of function $-\operatorname{Tr}(\theta^4N(\xi)^2)$. Hence

Proof. Selection. Consider three terms $(o^1,\mu)$, $(o^2,\nu)$, $(o^3,s)$ of rows 1, 2, 3 with positions summing to $X^*$. Put $\delta_{\mathrm{tr}}=\mu+\nu-s\in[-4,4]$ and $\delta_t=u(o_t^1)+u(o_t^2)+u(o_t^3)-\kappa_t$ with $\kappa_0=\kappa_1=5$, $\kappa_2=7$; by (D2), $\delta_0,\delta_1\in[-5,5]$. Then $0=\delta_{\mathrm{tr}}+5\delta_0+30\delta_1+180\delta_2$. Reduction modulo 5 gives $\delta_{\mathrm{tr}}=0$, then reduction modulo 6 gives $\delta_0=0$, then $\delta_1=0$, and finally $\delta_2=0$. Conversely these equalities give the target. So the contributing triples of terms are exactly those with $\mu+\nu=s$ and, in each digit $t$, heights summing to $\kappa_t$.

The control. The control (2) contributes only through triples with $p_2=0$ and $p_1+p_3=X^*$, where $p_1,p_3$ carry terms of rows 1 and 3 (otherwise a residue is 0). For such terms put $\delta'_{\mathrm{tr}}=\mu+(4-s)-4\in[-4,2]$ and $\delta'_t=u(o_t^1)+u(o_t^3)-\kappa_t$, with $\delta'_0,\delta'_1\in[-5,3]$ because the heights of $D_6$ in rows 1 and 3 lie in $[0,4]$ (D3). As above $\delta'_{\mathrm{tr}}=\delta'_0=\delta'_1=\delta'_2=0$, so the top heights of rows 1 and 3 would sum to 7, contradicting (T1). Hence the control does not contribute.

Expansion. By multilinearity of the determinant in its rows, the left side of (4) equals

over the contributing triples, where $a=x(o^1)$, $b=x(o^2)$, $c=x(o^3)$. Fix $(a,b,c)$. By (D1) for $D_6$ and $T_7$ applied digit by digit, the total sign of the option words with these values and digit sums $\kappa_t$ is $\prod_t w(a_t,b_t,c_t)$. For fixed $(a,b,c)$ the sum over $\mu+\nu=s$ is, expanding the determinant over permutations $\sigma$,

with $\alpha=\xi_{\sigma(1)}^{[a]}$, $\beta=\xi_{\sigma(2)}^{[b]}$, $\gamma=\xi_{\sigma(3)}^{[c]}$, because $\alpha\beta=\sum_{\mu,\nu}c_\mu(\alpha)c_\nu(\beta)\theta^{\mu+\nu}$ and the trace is $\mathbb{F}$-linear. Summing over $(a,b,c)$ and using that Frobenius is a ring endomorphism together with (1),

Hence the left side is

since $N V$ is alternating and lies in $\mathbb{F}$. Finally $6d=18$ is invertible because $r>18$. $\square$

The identity is checked by exact computation for random labels in anc/check_encoding.py.

Digit columns and the composite modulus

Parameters

Let $r>18$ be a prime and put

Let $B_2$ be a prime with $Q<B_2\le2Q$, where $Q=600k^2r^2M$ (it exists for large $r$ by Bertrand’s postulate), and set

Then $B=rB_2>600k^2r^3M=100A_0$, so $B-1\ge100A_0$; also $L_3<B_2$, $B_2\ne r$, and

Moreover $B\asymp r^6$, with constants depending only on $k$.

Random columns

A column is drawn as follows. Choose a label $\xi$ uniformly in $K^\times$. For rows $i=1,2$ and every position $0\le v<k$, let $d_{i,v}$ be the unique integer in $[1,r]$ congruent to $\rho_{i,v}(\xi)$ modulo $r$. For row $3$ and every $v$, choose $d_{3,v}$ uniformly from the $M$ integers in $[1,rM]$ congruent to $\rho_{3,v}(\xi)$, independently. Put $c_i=\sum_{v<k}d_{i,v}B^v\mathbin{\operatorname{mod}}h$. Different columns use independent labels and digits. Since $B\equiv0$ modulo both primes, $c_i\equiv d_{i,0}$ modulo $r$ and modulo $B_2$. In particular $c_1\equiv N(\xi)^2\ne0$ (mod $r$) by (3), and $c_1\equiv d_{1,0}\in[1,r]$ is a unit modulo $B_2$. By (3) the third row of $C$ mod $r$ is a multiple of the first, so $C$ mod $r$ always has rank at most two and $r\mid\det C$; this is harmless, since the obstruction below only uses $H_i\not\equiv0$ (mod $r$) and the divisor $E$ cancels in (11).

Smith forms modulo $h$

For a prime $p\mid h$ let $h_p=p^{k_p}$ be the $p$-part of $h$ ($k_r=k$, $k_{B_2}=k-1$). By the Chinese remainder theorem $\mathbb{Z}/h\mathbb{Z}=\mathbb{Z}/h_r\mathbb{Z}\times\mathbb{Z}/h_{B_2}\mathbb{Z}$ and $\operatorname{SL}_3(\mathbb{Z}/h\mathbb{Z})=\prod_p\operatorname{SL}_3(\mathbb{Z}/h_p\mathbb{Z})$. Since $C_{11}$ is a unit modulo both primes, [1 Lemma 4.1] applies to $C$ mod $h_p$ and gives $C\equiv P_p\operatorname{diag}(1,p^{b_p},p^{e_p})Q_p$ with $0\le b_p\le e_p\le k_p$, where $b_p\ge j$ if and only if all $2\times2$ minors of $C$ vanish modulo $p^j$. Put $D=\prod_p p^{b_p}$, $E=\prod_p p^{e_p}$ and $I=DE$. Let $\Lambda=\Lambda_C$ be the set of $v\in\mathbb{Z}^3$ whose reduction modulo $h$ lies in the row span of $C$.

The divisor moment

Proof. Write $b=b_{B_2}$ and $b'=b_r$. Since $p^\beta\le\sum_{i=0}^{\beta}p^i$,

Condition on the first column and on the first entries of the second and third columns. As $C_{11}$ is a unit modulo $p$, $b_p\ge j$ implies the two congruences $C_{3v}\equiv C_{31}C_{11}^{-1}C_{1v}\pmod{p^j}$, $v=2,3$, whose right sides are now fixed. We use only these two bottom entries, which have fresh independent digits.

The prime $B_2$. Modulo $B_2^j$ only the digits at positions $<j$ of an entry matter. The congruence modulo $B_2$ fixes $d_{3,0}$ modulo $B_2$, hence fixes $d_{3,0}$ since $1\le d_{3,0}\le rM<B_2$. Inductively, given the lower digits, the congruence modulo $B_2^{u+1}$ fixes $d_{3,u}B_2^u=r^uB_2^u d_{3,u}$ modulo $B_2^{u+1}$, hence $d_{3,u}$ modulo $B_2$ (as $r$ is invertible modulo $B_2$), hence $d_{3,u}$. Each digit has $M$ equally likely values, so the event $b\ge j$ fixes the bottom digits at positions $<j$ of both entries and has probability at most $M^{-2j}$.

The prime $r$. The event $b'\ge1$ is the deterministic event that $C$ mod $r$ has rank at most one. Write $d_{3,u}=\rho_{3,u}+rm_u$; the integers $m_u$ range over $M$ consecutive values, and $r\mid M$, so $m_u$ mod $r$ is uniform. Since $B^u=r^uB_2^u$, an entry is $\sum_u d_{3,u}r^uB_2^u=\sum_u\rho_{3,u}r^uB_2^u+\sum_um_ur^{u+1}B_2^u$. Its residue modulo $r^{t+1}$ ($1\le t\le k-1$) is therefore the residue modulo $r^{t+1}$ of a quantity determined by the residues $\rho_{3,u}$ and the $m_u$ with $u\le t-2$, plus $m_{t-1}B_2^{t-1}r^t$. As $B_2$ is invertible modulo $r$, given the congruence of the entry modulo $r^t$ and all $m_u$ with $u\le t-2$, the congruence modulo $r^{t+1}$ (whose right side is fixed) holds for exactly one value of $m_{t-1}$ mod $r$, hence with conditional probability $1/r$. The same holds for the second entry, with its own independent $m_{t-1}$.

Joint bound. Here $0\le j\le k-1$ and $0\le j'\le k$. The event $b\ge j$ depends only on the bottom digits at positions $<j$ and fixes them; it costs at most $M^{-2j}$, and the congruences modulo $r^t$ with $t\le j$ then cost nothing more. Next condition, in the order $t=j+1,\ldots,j'-1$, on the congruence modulo $r^{t+1}$: it involves $m_{t-1}$ with $t-1\ge j$, which is uniform modulo $r$ and independent of the event $b\ge j$ and of all digits at positions $\le t-2$, so by the previous paragraph each step costs a factor $1/r$ in each of the two entries. Therefore

The terms with $j'=0$ contribute at most $\sum_j(B_2/M^2)^j\le2$. If $\operatorname{rank}(C\mathbin{\rm mod}r)\le1$, the terms with $j'\ge1$ contribute at most

using (7).

Let $\mathcal J$ be the event that some integer in $[-\tau,\tau]$ is congruent to $\det C$ modulo $h$.

Proof. By Lemma 3.1, $\mathcal J$ requires two equal labels. Exactly two labels coincide with probability at most $3/(r^3-1)\le 4r^{-3}$. By (3) the columns of $C$ mod $r$ are $\mathbb{N}(\xi_j)^2(1,\varphi(\xi_j),-\operatorname{Tr}\theta^4)^\mathsf{T}$, two of them equal; the rank is at most one only if the third label has the same value of $\varphi$, which has conditional probability at most $(r^2-1)/(r^3-2)\le1/r$ (the number of $\xi\ne\xi_1$ with $\varphi(\xi)=\varphi(\xi_1)$ is $r^2-1$ or $r^2-2). By Lemma 3.3 this case contributes at most $4r^{-3}(2+6r\cdot r^{-1})=32r^{-3}$. Three equal labels have probability at most $2r^{-6}$ and contribute at most $2r^{-6}(2+6r)$.

:::

The auxiliary modulus

Put $H=2h$ and choose a prime $q$ with $h^{6}<q\leq2h^{6}$. Let $w=\lfloor q/(1000H^{2})\rfloor$. Choose a nonsquare $\nu\in\mathbb{F}_{q}$ and put

This is the slab cap of [2]. A line meets the graph of $x^{2}-\nu y^{2}$ in at most two points (the restriction is a quadratic with nonzero leading coefficient $x_{0}^{2}-\nu y_{0}^{2}$ for a direction with $(x_{0},y_{0})\neq0$, and vertical lines meet once), so $S$ has no three collinear points. Since $q\geq2000H^{2}$,

The allowed shifts $\mathcal{A}=\{a\in\mathbb{F}_{q}^{3}:\lVert ma_{1}\rVert_{q}>3Hw\text{ for }1\leq m\leq3H\}$, the random set $\mathcal{V}=G_{q}(a+S)$ with $a$ uniform in $\mathcal{A}$ and $G_{q}$ uniform in $\operatorname{GL}_{3}(\mathbb{F}_{q})$, and the weight

are as in [1 Section 5]; the same analysis for the slab is written out in [3 Section 3.4]. Lemma 5.2 of [1] is stated for $S\subset\{0,\ldots,w-1\}^{3}$, but its proof uses the box only through the first coordinate. Indeed: (a) a uniform shift violates the condition for a given $m$ with probability $(6Hw+1)/q$, so $\Pr(a\notin\mathcal{A})\leq3H(6Hw+1)/q<1/2$, which does not involve $S$; (b) if $a+v=0$ with $v\in S$, then $\lVert a_{1}\rVert_{q}=\lVert v_{1}\rVert_{q}\leq w-1$, contrary to $m=1$; (c) a relation $\sum_i x_i u^{(i)}=0$ with $u^{(i)}=G_q(a+v^{(i)})$, $0<|x|\leq H$ and $m=\sum x_i\neq0$ gives $ma_1=-\sum_i x_i v_1^{(i)}$, of absolute value at most $3H(w-1)$ because $0\leq v_1^{(i)}<w$, again a contradiction; (d) if $m=0$ the relation contradicts the affine independence of distinct points of $\mathcal{V}$, which follows from the line property. The proof of [1 Proposition 5.3] uses only the affine invariance of the line property, the transitivity of the affine group on affinely independent triples, and $|S|=s$. We obtain: $|\mathcal{A}|\geq q^{3}/2$; $0\notin\mathcal{V}$; a relation $\sum x_i u_q^{(i)}=0$ in $\mathbb{F}_{q}^{3}$ with $0<|x|\leq H$ is impossible for three distinct points of $\mathcal{V}$; and

If $W(A)>0$ then no column of $A\mathbin{\bmod}q$ is zero, and the columns are either affinely independent or two of them are equal.

Weighted lattice counts

Fix $C$ with the data $D,E,I,\Lambda$ of Lemma 3.2, and an integer $N\geq h$ with $hq\mid N$. Let $\mathcal{B}=([0,N)^{2}\times[N,2N))\cap\mathbb{Z}^{3}$ and $\pi(u)=(u_{1}/u_{3},u_{2}/u_{3})$.

Proof. If $t\neq0$, then $0<|t|\leq\tau<q$, so $A\mathbin{\bmod}q$ has rank three and $W(A)\ll1$; every row has length $<4N$ and $\lambda_{3}(\Lambda)\leq E\leq h<4N$, so [1 Proposition 2.5] with $X=4N$ gives the bound.

Let $t=0$. We follow the proof of [1 Proposition 7.1]. The matrix has rational rank two, and its primitive null vector $x$ has all coordinates nonzero and $|x|\ll N^{2}$. Put $\Lambda_x=\Lambda\cap x^{\perp}$, $x\cdot\Lambda=g(x)\mathbb{Z}$ and $J_x = I|x|/g(x)$. Then $g(x) \mid E$, so $g(x)^3/I \le E^2/D \le h^2$, and $\Lambda_x$ reduces onto the plane $\Pi_x \subset\mathbb{F}_q^3$ orthogonal to $x$ because $q \nmid E$ [1 Lemma 7.2]. For a sublattice of index $m$ in $\Lambda_x$, the number of rank-two row triples of length $\le4N$ is $\ll N^6/(mJ_x^3)$.

Moment. For $Y \ge h$, $\sum_{Y\le|x|<2Y} g(x)^3 \ll Y^3I$. Indeed $g^3 \le\sum_{m\mid g}m^3$ over $m=\prod_p p^{j_p}$ with $j_p\le e_p$, and by Lemma 3.2 the vectors with $m\mid g(x)$ form a union of residue classes modulo $m$ of proportion $\prod_p p^{-j_p-\max(j_p-b_p,0)}$; since $m\le E\le h\le Y$ each class has $\ll(Y/m)^3$ vectors of length $<2Y$. Hence the sum is $\ll Y^3\prod_p\sum_{j\le e_p}p^{2j-\max(j-b_p,0)}\ll Y^3\prod_p p^{b_p+e_p}=Y^3I$, each inner sum being dominated by its last term.

Split the null vectors into $O(\log2N)$ dyadic shells $Y\le|x|<2Y$; for fixed $x$ and index $m$ the count is $\ll N^6g(x)^3/(m^3I^3Y^3)$. The cases are those of [1 Proposition 7.1], with (8) in place of $q^3/s\ll qh^{12}$:

• affinely independent residues: $|x|>H$, so $Y>H/2=h$; with $m=1$, $W\ll1$ and the moment bound, the shell contributes $\ll N^6/I^2$;

• an equal pair $i,j$ with $x\bmod q\notin\mathbb{F}_q(e_i-e_j)$: rows lie in an index-$q$ sublattice, there are $\ll Y^3$ normals, and with $g^3\le Ih^2$ and $W\ll(q^3/s)^2$ the shell contributes $\ll(N^6/I^2)h^2q^{-3}(q^3/s)^2\ll(N^6/I^2)h^6/q\le N^6/I^2$;

• an equal pair with $x\bmod q\in\mathbb{F}_q(e_i-e_j)$: then $Y>q/2$ and there are $\ll Y^3/q^2$ normals; rank $\ge2$ modulo $q$ gives $\ll(N^6/I^2)h^2q^{-2}(q^3/s)\ll(N^6/I^2)h^4/q$, and rank $\le1$ (rows in one of $q+1$ lines, each of index $q$) gives $\ll(N^6/I^2)h^2q^{-4}(q^3/s)^2\ll(N^6/I^2)h^6/q^2$.

Since $q>h^6$ all contributions are $\ll N^6/I^2$ per shell.

Sampling, deletion and the exponent

Sampling

Let $s_0=479$ and

This is an integer divisible by $hq$, and $N\ge h$. Choose $G_h$ uniformly in $\mathrm{SL}_3(\mathbb{Z}/h\mathbb{Z})$ and $\mathcal{V}$ as in § 4, independently. Given these shared choices, each sample draws a fresh column $c$ as in § 3, a fresh uniform element of $\mathcal{V}$, and a uniform $u\in\mathcal{B}$ with $u\equiv G_hc\pmod h$ and $u\bmod q$ equal to that element. Each prescribed residue pair has exactly $(N/(hq))^3$ lifts. The exact lifting identity [1 Lemma 6.2] holds verbatim: conditional on $\mathcal{C}$ and the labels,

A triple is bad if its projections are pairwise distinct and $|\det A|\le\tau$. Since $2\tau<h$, at most one determinant value in $[-\tau,\tau]$ is possible, and none unless $\mathcal{J}$ occurs. By Lemma 3.2, Proposition 5.1 and Corollary 3.4,

For two samples, $\Pr(\pi(u)=\pi(v))\ll(hq)^6N^{-3}$ [1 Lemma 6.1].

Deletion

Fix $\gamma= 354042/354043 < 1$, put $a_r = r^\gamma\sqrt{N^3/\tau}$, $n_r = \lfloor a_r \rfloor$, and take $2n_r$ samples. Let $Z$ count the pairs with equal projections and the bad triples. Then

For the first term, $N^{3/2}=(hq)^6B^{-3s_0/2}$ and $\tau\geq B^{k-1}/3$, so

because $3s_0-(k-1)=1437-1439=-2$ and $B\gg r^6$. For the second term, $n_r^2\leq r^{2\gamma}N^3/\tau$ and $h/\tau\leq3r$, so it is $\ll(\log2N)^2r^{2\gamma-2}\to0$, since $\log2N\ll\log r$ and $\gamma<1$. Hence $\mathbb{E}Z<n_r$ for all large $r$. Deleting one index from each counted pair or triple leaves at least $n_r$ samples whose projections are distinct and whose triples satisfy $|\det A|>\tau$. Every coordinate $u_3$ lies in $[N,2N)$, so the projective area identity gives

for a set $P_r$ of $n_r$ points.

The exponent

We have $h=rB^{k-1}$, $h^6<q\leq2h^6$, $B\asymp r^6$ and $\tau\asymp B^{k-1}$. Hence

So $a_0r^\alpha\leq n_r\leq b_0r^\alpha$ for constants $a_0,b_0>0$ and all large primes $r$, and $n_r^2\Delta(P_r)\geq r^{2\gamma}/64\geq c n_r^{2\gamma/\alpha}$. With $\gamma=354042/354043$,

Every cardinality

Given a large $n$, let $y=(n/a_0)^{1/\alpha}$ and choose a prime $r\in(y,2y]$. Then $n\leq n_r\leq C_0n$ with $C_0=2^\alpha b_0/a_0$. Keeping $n$ points of $P_r$ does not decrease the minimum area, so $\Delta(n)\geq\Delta(P_r)\geq c n_r^{-2+\eta}\geq cC_0^{-2+\eta}n^{-2+\eta}$. This proves Theorem 1.1. □

Remarks

Where the gain comes from. In [1, 2, 3] the modulus is $h=B^k$ and the obstruction excludes $[-\tau,\tau]$ with $h/\tau\asymp B$; the collision probability must beat $Br^{2\gamma}$, which forces $d=5$ even with the fresh-digit refinement. With $B\equiv0\pmod r$ the information “$\gamma^{k-1}\not\equiv0\pmod r$” already excludes the window for the smaller modulus $rB^{k-1}$, so only $r^{2\gamma}$ must be beaten. The digit lengths, the cap and the lift box are unchanged from [2, 3].

The value of $\gamma$. Any $\gamma< 1$ works in the deletion step; the choice $\gamma= 354042/354043$ gives the clean value $1/177022$, and the exponents obtained approach $2/354043$. With $\gamma$ this close to 1 the second term in the deletion step is small only once $(\log r)^{2\gamma-2/354043}$ is, so $n_0$ is astronomically large; this does not affect the theorem.

Checks. The ancillary files contain: the design check (check_design.py); the exact identity (4) and the column (3) for random labels with $d = 3$, $r = 23$ (check_encoding.py); an end-to-end test that builds the actual integer digit columns with the parameters (3.1)–(3.2) for $r = 23$ and verifies Lemma 3.1 (check_obstruction.py); and the exponent arithmetic (exponent.py).

Status. This note has not been refereed.