Open MathsAll courses

A cap at an auxiliary prime

Written by Claude Opus 5.5 (Anthropic), October 2026. Self-checked by the writing AI. Public domain (CC0).

The determinant obstruction of A determinant obstruction from field norms works modulo \(h\) and cannot see determinant zero: three integer columns can be linearly dependent while their residues modulo \(h\) are not. This lesson adds a second, independent condition at a large prime \(q\). The residues modulo \(q\) of the sampled columns are taken from a random set \(V\subseteq\mathbb F_q^3\) with no three points on a line, obtained from a piece of an elliptic quadric by a restricted random translation and a random invertible linear map. Three distinct points of \(V\) then admit no short integer linear relation; and the probability that prescribed residues lie in \(V\) is bounded in three regimes, according to how degenerate the residues are. These bounds feed the zero-determinant count of the seventh lesson.

We use primes in intervals (Lemma 4.3 of Small triangles and the plan) and elementary linear algebra over the field \(\mathbb F_q\): \(\mathrm{GL}_3(\mathbb F_q)\) acts transitively on ordered pairs of linearly independent vectors (extend each pair to a basis), and the affine maps \(v\mapsto Gv+c\) act transitively on ordered affinely independent triples, those \((u^{(1)},u^{(2)},u^{(3)})\) with \(u^{(2)}-u^{(1)}\) and \(u^{(3)}-u^{(1)}\) linearly independent. For a group acting transitively on a finite set and a uniform group element \(g\), the point \(g^{-1}x_0\) is uniform on the set (all fibres of \(g\mapsto g^{-1}x_0\) are cosets of one stabilizer).

1. A cap in a box

Lemma 1.1 (cap). Let \(q\) be an odd prime and \(1\leq w\leq q\). There is a set \(S\subseteq\{0,\ldots,w-1\}^3\subseteq\mathbb F_q^3\) with \(|S|\geq w^3/q\) such that no affine line of \(\mathbb F_q^3\) contains three distinct points of \(S\).

Proof. Choose a nonsquare \(\nu\in\mathbb F_q\), put \(Q(x,y)=x^2-\nu y^2\) and \(\Gamma=\{(x,y,Q(x,y)):x,y\in\mathbb F_q\}\), a set of \(q^2\) points. \(Q\) vanishes only at \((0,0)\): if \(y\neq0\) and \(Q(x,y)=0\), then \(\nu=(x/y)^2\) would be a square. Let \(\{p+tv:t\in\mathbb F_q\}\) be a line. If \((v_1,v_2)\neq(0,0)\), its points on \(\Gamma\) satisfy \(p_3+tv_3=Q(p_1+tv_1,p_2+tv_2)\), a quadratic equation in \(t\) with leading coefficient \(Q(v_1,v_2)\neq0\): at most two solutions. If \((v_1,v_2)=(0,0)\), the line meets \(\Gamma\) once. Translates of \(\Gamma\) have the same property.

For \(b\) uniform in \(\mathbb F_q^3\), a point \(x\) lies in \(b+\Gamma\) exactly when \(b\in x-\Gamma\), with probability \(q^2/q^3=1/q\). So the expected number of points of the box \(\{0,\ldots,w-1\}^3\) in \(b+\Gamma\) is \(w^3/q\), and some \(b\) gives at least this many. Let \(S\) be the intersection of that translate with the box. \(\square\)

Parameters. Let \(h\geq2\) be the main modulus, and put \[ \begin{gathered} H=h^2,\\ h^{100}<q\leq2h^{100},\\ w=\Bigl\lfloor\frac q{1000H^2}\Bigr\rfloor , \end{gathered}\tag{1.1} \] with \(q\) prime. Such \(q\) exists for large \(h\) by Lemma 4.3 of the first lesson; then \(q\geq2000H^2\) and \(\frac q{2000H^2}\leq w\leq\frac q{1000H^2}\). We identify \(0,\ldots,w-1\) with their residues. Fix a set \(S\) as in Lemma 1.1, chosen before any randomness, and let \(s=|S|\); then \[ s\geq\frac{w^3}q\geq\frac{q^2}{2000^3H^6}.\tag{1.2} \]

2. Allowed shifts and the random set

For \(t\in\mathbb F_q\) let \(\|t\|_q\) be the least absolute value of an integer representative of \(t\). Let the set \(\mathcal A\) of allowed shifts consist of all \(a\in\mathbb F_q^3\) such that, for every \(1\leq m\leq3H\), \[ \|ma_1\|_q>3Hw;\tag{2.1} \] choose \(a\) uniformly in \(\mathcal A\) and, independently, \(G_q\) uniformly in \(\mathrm{GL}_3(\mathbb F_q)\), and put \[ V=G_q(a+S).\tag{2.2} \]

Lemma 2.1 (the random set). Let \(H\geq1\), \(q\geq2000H^2\) prime, \(w=\lfloor q/(1000H^2)\rfloor\), and \(S\subseteq\{0,\ldots,w-1\}^3\) without three distinct collinear points.

(a) \(|\mathcal A|\geq q^3/2\).

(b) For every \(a\in\mathcal A\) and invertible \(G_q\), \(|V|=|S|\), \(0\notin V\), and \(V\) has no three distinct collinear points.

(c) Let \(x\in\mathbb Z^3\setminus\{0\}\) with \(|x|\leq H\), and \(u^{(1)},u^{(2)},u^{(3)}\in V\). The relation in \(\mathbb F_q^3\) \[ \sum_{j=1}^3x_ju^{(j)}=0\tag{2.3} \] is impossible if \(x_1+x_2+x_3\neq0\), and, if \(x_1+x_2+x_3=0\), it is impossible whenever the three points are affinely independent. In particular (2.3) is impossible for three distinct points of \(V\).

Proof. (a) Since \(3Hw\leq3q/(1000H)<q/2\), the residues \(t\) with \(\|t\|_q\leq3Hw\) number exactly \(6Hw+1\). For each \(1\leq m\leq3H<q\), multiplication by \(m\) is a bijection of \(\mathbb F_q\), so a uniform \(a\) violates the condition for \(m\) with probability \((6Hw+1)/q\). By the union bound, \[ \begin{aligned} \Pr(a\notin\mathcal A)&\leq\frac{3H(6Hw+1)}q\\ &\leq\frac{18}{1000}+\frac3{2000H}<\frac12 . \end{aligned} \] (b) Invertible affine maps preserve cardinality and lines. If \(a+v=0\) with \(v\in S\), then \(\|a_1\|_q=\|v_1\|_q\leq w-1\leq3Hw\), contradicting the condition with \(m=1\); so \(0\notin a+S\), and \(0\notin V\).

(c) Write \(u^{(i)}=G_q(a+v^{(i)})\) with \(v^{(i)}\in S\) and \(m=x_1+x_2+x_3\in\mathbb Z\). Applying \(G_q^{-1}\) to (2.3) and taking first coordinates gives \(ma_1=-\sum_ix_iv^{(i)}_1\) in \(\mathbb F_q\). If \(m\neq0\), then \(1\leq|m|\leq3H\), and the integer \(-\sum_ix_iv^{(i)}_1\) (with representatives \(0\leq v^{(i)}_1<w\)) has absolute value at most \(3H(w-1)\); so \(\||m|a_1\|_q=\|ma_1\|_q\leq3Hw\), contradicting \(a\in\mathcal A\). If \(m=0\), the residues of \(x_1,x_2,x_3\) are not all zero (since \(0<|x_i|\leq H<q\) for some \(i\)) and add up to zero; substituting \(x_3=-x_1-x_2\) gives \(x_1(u^{(1)}-u^{(3)})+x_2(u^{(2)}-u^{(3)})=0\) with \((x_1,x_2)\not\equiv(0,0)\), so the triple is not affinely independent. Three distinct points of \(V\) are affinely independent by (b). \(\square\)

3. Inclusion weights

For an integer \(3\times3\) matrix \(A\) let \(\rho(A)\) be the probability, over \(a\) and \(G_q\) with \(S\) fixed, that all three columns of \(A\bmod q\) lie in \(V\), and define the weight \[ W(A)=\Bigl(\frac{q^3}s\Bigr)^3\rho(A).\tag{3.1} \] The normalization makes \(W\) about one for generic columns.

Proposition 3.1 (weights). There is an absolute constant \(C\) such that:

If \(W(A)>0\), no column of \(A\bmod q\) is zero, and the columns are affinely independent or two of them are equal. If the columns are affinely independent and \(W(A)>0\), there is no \(x\in\mathbb Z^3\setminus\{0\}\) with \(|x|\leq H\) and \(Ax\equiv0\pmod q\).

Proof. Removing the restriction on \(a\). If \(a\) is uniform in all of \(\mathbb F_q^3\), then, given \(G_q\), \(G_qa\) is uniform, so \(v\mapsto G_qv+G_qa\) is a uniform element of the affine group. Conditioning on the event \(a\in\mathcal A\), of probability at least \(\frac12\) (Lemma 2.1(a)), at most doubles the probability of any event.

Affinely independent columns. For a uniform affine map \(g\) the inverse image of a fixed affinely independent ordered triple is uniform among the \(q^3(q^3-1)(q^3-q)\) such triples; the triple lies in \(g(S)\) exactly when its inverse image lies in \(S^3\), which contains at most \(s^3\) of them. So \[ W(A)\leq\frac{2q^9}{q^3(q^3-1)(q^3-q)}\leq C . \] Rank at least two. Fix any allowed \(a\) and put \(S_a=a+S\). If two of the target columns are linearly independent, their inverse image under a uniform \(G_q\) is uniform among the \((q^3-1)(q^3-q)\) ordered independent pairs, of which at most \(s^2\) lie in \(S_a^2\); requiring the third column too only lowers the probability. So \(W(A)\leq\frac{q^9}{s^3}\cdot\frac{s^2}{(q^3-1)(q^3-q)}\leq C\frac{q^3}s\) for each allowed \(a\), and hence after averaging over \(a\).

All matrices. A zero target column never lies in \(V\) (Lemma 2.1(b)). Otherwise fix one nonzero target column; its inverse image under \(G_q\) is uniform among the \(q^3-1\) nonzero vectors, and \(S_a\) consists of \(s\) nonzero vectors. So \(W(A)\leq\frac{q^9}{s^3}\cdot\frac s{q^3-1}\leq C(q^3/s)^2\).

Support. If \(W(A)>0\), some outcome puts all three columns in \(V\): none is zero, and if they are pairwise distinct they are affinely independent (no three collinear points in \(V\)); otherwise two are equal. For affinely independent columns in \(V\), Lemma 2.1(c) excludes \(Ax\equiv0\) with \(0<|x|\leq H\). \(\square\)

How the weights are used. In the sampling of the sixth lesson, \((a,G_q)\) is chosen once, independently of everything at the main modulus, and every sampled column gets its residue modulo \(q\) uniformly from \(V\), independently. Since \(|V|=s\) for every outcome, a prescribed ordered triple of residues, repetitions allowed, is obtained with probability \[ \frac{\rho(A)}{s^3}=\frac{W(A)}{q^9},\tag{3.2} \] where \(A\) is any integer matrix with these residues as columns. The value does not change when conditioning on anything at the main modulus.

4. Exercises

4.1. For \(q=3\) and \(\nu=2\), list \(\Gamma\) and check directly that no line of \(\mathbb F_3^3\) meets it in three points.

4.2. Why is the translation \(a\) restricted? Suppose \(a=0\) and \(S\) contains points \(v,v',v''\) with \(v''=v+v'\) as integer vectors. Find a short relation (2.3) among three points of \(V\) whose coefficients do not add up to zero, and explain how the condition \(a\in\mathcal A\) excludes it.

4.3. Show that the three bounds of Proposition 3.1 are of the right order: for a generic \(A\), \(W(A)\) is close to \(1\).

4.4. Check the identity (3.2) in a tiny case: \(S\) with two points, and a target triple with all three columns equal.

4.5. In the proof of Proposition 3.1, why does conditioning on \(a\in\mathcal A\) at most double probabilities?

5. Solutions

4.1. Over \(\mathbb F_3\), \(-2=1\), so \(Q(x,y)=x^2+y^2\) and \(\Gamma\) consists of the nine points \((x,y,x^2+y^2)\): third coordinate \(0\) at \((0,0)\), \(1\) at the four points with exactly one of \(x,y\) nonzero, and \(2\) at the four points with both nonzero. A line with direction \((v_1,v_2,v_3)\), \((v_1,v_2)\neq(0,0)\), meets \(\Gamma\) at the roots of a quadratic in the parameter with leading coefficient \(v_1^2+v_2^2\neq0\) (as \(-1\) is not a square modulo \(3\)), so at most two points; a line with direction \((0,0,1)\) meets \(\Gamma\) once.

4.2. With \(a=0\), \(G_qv+G_qv'-G_qv''\) equals \(G_q(v+v'-v'')=0\): the relation \(x=(1,1,-1)\), of norm \(\sqrt3\leq H\), with coefficient sum \(1\). For \(a\in\mathcal A\) the same three points of \(S\) give points \(G_q(a+v)\), and the relation would force \(1\cdot a_1=-(v_1+v'_1-v''_1)=0\), so \(\|a_1\|_q=0\leq3Hw\), which \(\mathcal A\) excludes. In general a coefficient sum \(m\neq0\) leaves the term \(ma_1\), which the restriction keeps away from the small integers that the points of \(S\) can produce.

4.3. For three columns in general position, the probability that a uniform affine image of \(S\) contains them is about \(s^3/q^9\) (each of three nearly independent events of probability \(s/q^3\)), so \(W\approx1\); the bound \(C\) loses only the factor \(2\) from the restriction and the ratio \(q^9/(q^3(q^3-1)(q^3-q))\).

4.4. All three residues equal \(t\): the probability that three independent uniform choices from \(V\) all equal \(t\) is \(\mathbf 1\{t\in V\}/s^3\), whose expectation is \(\Pr(t\in V)/s^3\), and \(W(A)/q^9=\Pr(t\in V)/s^3\) by (3.1).

4.5. For an event \(E\) and \(a\) uniform in \(\mathbb F_q^3\), Lemma 2.1(a) gives \(\Pr(a\in\mathcal A)\geq\frac12\), so \[ \begin{aligned} \Pr(E\mid a\in\mathcal A)&=\frac{\Pr(E\cap\{a\in\mathcal A\})}{\Pr(a\in\mathcal A)}\\ &\leq2\Pr(E). \end{aligned} \]

References