Section 3.16 · PDF pages 52–55
Selecting the first set with the required shares
The notation transcription is provisional. Check it against the printed mathematics when citing or reusing a formula.
3.16 Selecting the first set with the required shares
The finite selection argument must control a single set simultaneously for all primes in its weighted sum. We give its orbit conditions explicitly. For x > 1, ϵ > 0, set
Selectable PDF notation • transcription unchecked
h = 2 + 8ϵ, K =⌈^{8(h + 2)}_{ϵ} ⌉, r = K + 1, δ = x^{−ϵ/8}, u = ⌈1/δ⌉.The r in this paragraph is the fixed orbit parameter, not the varying rank also denoted by r elsewhere. Define
M_{0} = ⌈(h + 3) log x 10^{6r+1}⌉, ℓ_{0} = (6r + 1)u,
Selectable PDF notation • transcription unchecked
⌈ ⌉
G^{′}= (M_{0} + 5)ℓ_{0}, N_{1} = max{6e G^{′}δ, (h + 3) log_{2} x} + 1.
For U ⊂{0, . . . , n −1}, a cyclic window of length L starting at i is the image of {i, . . . , i + L −1} modulo n. A tile s is the integer interval [sℓ_{0}, (s + 1)ℓ_{0}), divided into 6r + 1 successive cells of length u, numbered from 1. It is marked if the odd cells miss U, while each even cell contains exactly one point of U, at an even integer. Call U good, for parameter L_{2}, if:
1. every cyclic L_{2}-window contains at most K points;
2. for every tile index s_{0} < ⌊n/ℓ_{0}⌋, some one of the next M_{0} + 1 tile indices, read cyclically modulo ⌊n/ℓ_{0}⌋, is marked;
3. every cyclic G^{′}-window contains at most N_{1} points.
These are precisely the three conditions in Formalism/SubspaceCounting/GoodOrbitIntervalTileCondition.lean:10--25 with the parameters of Formalism/SharpRestriction/GrowthBounds/UnramifiedQuadraticSetting.lean:239--252.
Lemma 3.36 (The finite orbit probability bound). Fix ϵ, C_{o}, L_{b} > 0. There are C_{b}, x_{0} > 0, depending only on these constants, such that for x ≥x_{0},
Selectable PDF notation • transcription unchecked
x^{ϵ/4}≤n ≤C_{o}x^{h}, L_{2} ≤L_{b},and independent inclusion probabilities 3δ/4 ≤ p_{i} ≤ δ, the probability that the selected set is not good, conditional on any one point being selected, is at most C_{b}x^{−2}.
Proof. It is enough to prove the following bound, before substituting the parameters:
Selectable PDF notation • transcription unchecked
(_{L} ) ∑G^{′} (_{G′})_{′}
n^{2} δ^{K}+ n(1 −π_{0})^{M0}+ n δ^{j}(1 −δ)^{G−j}, (67)
^{K} j=N_{1}−1^{j}where
Selectable PDF notation • transcription unchecked
[_{3δ} ]3r
π_{0} = [(1 −δ)^{u}]^{3r+1} ⌊u/2⌋_{4 }(1 −δ)^{u−1} .For the first term, if an L_{2}-window contains more than K points after forcing the chosen point, the other points contain a( ) K-subset of that window. Each such subset is selected with probability at most δ^{K}; there are at most ^{L}_{K}^{2} possibilities. Sum over the n initial positions. For the third term the forced point changes the count by at most one. Independent variables with probabilities at most δ are dominated by independent Bernoulli variables of parameter δ: this follows coordinate by coordinate, since the expectation of any in-creasing function is affine and nondecreasing in each probability. Padding a window to G^{′} points can only increase its upper tail. The binomial tail in (67) follows.
For a single tile, independence gives at least (1 −δ)^{u} for an empty cell. An even cell has at least ⌊u/2⌋ available even positions. Requiring one specified position and excluding all others has probability at least (3δ/4)(1 −δ)^{u−1}. These alternatives are disjoint, and the cells are disjoint, proving the lower bound π_{0} for a marked tile. Among M_{0} + 1 successive tile indices, at most one contains the forced point. The other at least M_{0} tiles are unaffected and independent. Their failure probability is at most (1−π_{0})^{M0}. The condition (M_{0} + 1)ℓ_{0} ≤n ensures that their cyclic indices are distinct. There are at most n starting tile indices, giving the second term. This proves (67), including the conditional probability at the forced point. It is the argument of ThickFrames/NotGoodLe.lean:20--138 and TilesLe.lean:26--105.
We now check the numerical bounds, uniformly in n, L_{2}. For large x, 0 < δ ≤1/100 and 1 ≤uδ ≤1+δ. Using log(1 −δ) ≥−δ/(1 −δ) gives (1 −δ)^{u} ≥e^{−1.03} > 3/10. Also ⌊u/2⌋δ ≥(1 −δ)/2 ≥99/200. Thus each of the two bracketed factors defining π_{0} is at least 1/10, and at most 1. Consequently
Selectable PDF notation • transcription unchecked
10^{−(6r+1)}≤π_{0} ≤1, (1 −π_{0})^{M0}≤e^{−M0π0}≤x^{−(h+3)}.These are the estimates of ThickFrames/MarkedLowBounds.lean:6--95. Since Kϵ/8 ≥h + 2,
Selectable PDF notation • transcription unchecked
(L_{2})δ^{K}≤ max(L_{b}, 1)^{K}x^{−(h+2)}.
Selectable PDF notation • transcription unchecked
K
For the last tail put J = N_{1} −1. The factorial bound j! ≥(j/e)^{j} and J ≥6e G^{′}δ show, for j ≥J,
Selectable PDF notation • transcription unchecked
(_{G}′)_{′}
_{j} δ^{j}(1 −δ)^{G−j}≤(eG^{′}δ/j)^{j}≤6^{−j}.Their geometric sum is at most e^{−J} when J ≥ 1; the J = 0 case is bounded by the full binomial sum 1. As J ≥(h + 3) log_{2} x, this is at most x^{−(h+3)}. Multiplying these three bounds by n ≤C_{o}x^{h} proves the claimed C_{b}x^{−2}, for example with C_{b} = (|C_{o}| + 1)(max(L_{b}, 1)^{K}+ 2). Finally
(M_{0} + 1)ℓ_{0} = O_{ϵ}((log x + 1)x^{ϵ/8}) ≤x^{ϵ/4}≤n
eventually, so the tile-size condition used above is indeed satisfied at the same uniform threshold. This is the parameter calculation of ThickFrames/orbitTerms.lean:97--261.
Proposition 3.37 (One set controls every weighted orbit). Fix 0 < ϵ < 1/52 and C_{o} ≥ 2. There are C_{b}, x_{0} > 0 with the following property. Let A be any finite abelian group with subgroup A_{0} of index o ≤C_{o}, and put n = |A|, n_{0} = |A_{0}|. Suppose
Selectable PDF notation • transcription unchecked
_{2}^{1}x^{2+8ϵ} ≤n ≤C_{o}x^{2+8ϵ}, x ≥x_{0}.For each member p of any finite index set P, choose an element h_{p} ∈A of order at least x^{ϵ/4}, a nonnegative weight ω_{p}, and an orbit origin b(h_{p}, t) on the orbit of each t. Suppose L_{2} ≤2(620C_{o}/ϵ + 1). There is a single subset T ⊂A satisfying
Selectable PDF notation • transcription unchecked
||^{1}_{2}δn ≤|T||| ≤2δn, (68)
∑ |T ∩(γ + A_{0})| −λ(γ)|T| ≤x^{−1+ϵ}|T| ∑ (γ ∈A), (69)ω_{p}|{t ∈T : the h_{p}-orbit at t is not good}| ≤4C_{b}x^{−2}δn ω_{p}, (70)
Selectable PDF notation • transcription unchecked
p∈P p∈P
where λ(γ) = 4/(3o + 1) on A_{0}, and 3/(3o + 1) on its other cosets. Goodness uses the explicit orbit conditions above.
Proof. Select each a ∈A independently with probability δ on A_{0} and 3δ/4 elsewhere. For every coset c, let Y_{c} be the discrepancy between its selected count and its expected count. Independence gives
Selectable PDF notation • transcription unchecked
E∑Y_{c}^{2}=∑p_{a}(1 −p_{a}) ≤δn.
c a∈AFor a fixed p, t, translation identifies the orbit of h_{p} with Z/ ord(h_{p})Z. The indices on the orbit are distinct, and the origin hypothesis puts t at one of these indices. Conditional on its inclusion the other orbit probabili-ties remain independent in [3δ/4, δ]; variables outside the orbit sum to total mass one. Lemma 3.36 therefore gives
Pr(t ∈T and its p-orbit is bad) ≤δC_{b}x^{−2}.
Its upper order bound is automatic from ord(h_{p}) ≤ n ≤ C_{o}x^{2+8ϵ}. Consequently, if B(T) denotes the weighted bad count on the left of (70), then EB(T) ≤m, where m = C_{b}x^{−2}δn∑_{p}ω_{p}.
Selectable PDF notation • transcription unchecked
√
Put D = 2δn. When m > 0, the nonnegative objective
Selectable PDF notation • transcription unchecked
∑_{c}Y_{c}(T)^{2} B(T)
D^{2+} 4mhas expectation at most 3/4. A finite weighted average has some positive-mass outcome no greater than its average. That outcome has |Y_{c}| ≤D for every coset and B(T) ≤4m. When m = 0, B(T) = 0 on every positive-mass outcome since it is nonnegative with expectation zero; select one with ∑_{c}Y^{ 2}_{c} ≤D^{2}. This also proves the same conclusions. This is the single-objective finite selection in ThickFrames/select.lean:70--174; in particular the set does not depend on a later choice of p.
We verify the shares and size bounds after normalizing by the actual |T|. The expected count in A_{0} is δn_{0}; in another coset it is 3δn_{0}/4. Thus, with µ = (3o + 1)δn_{0}/4,
Selectable PDF notation • transcription unchecked
|||T| −µ|| ≤oD.
For large x we have 64C_{o}^{4}≤x^{ϵ}. The lower bound on n then implies
Selectable PDF notation • transcription unchecked
32o^{4}x^{2}≤δn, 4oD ≤x^{−1}δn_{0}.The second inequality is the square root of the first after substituting D^{2} = 2δn and n_{0} = n/o. It follows that oD ≤δn_{0}/4, so 3δn/4 ≤|T| ≤2δn; in particular (68) holds. If w = 4 on the distinguished coset and w = 3 otherwise, its discrepancy from w|T|/(3o + 1) is at most
Selectable PDF notation • transcription unchecked
D +_{3}^{woD}_{o + 1} ≤3D ≤x^{−1}|T|.For the last step, 3D ≤3x^{−1}δn_{0}/(4o) ≤x^{−1}(3δn/4). Since x^{−1}≤x^{−1+ϵ}, this proves (69). The weighted bad bound was already obtained by the selection. These computations are the normalization in ThickFrames/SharesOfCounts.lean:6--112 and topsGroup.lean:64--143.
For the host application, every prime classified as inert in the distinguished quadratic field is greater than Y^{ϵ/5}: the pair conditions make every smaller prime split, including 2. If x^{1/J} ≤Y ≤x and J ≤C_{o}, such a prime is greater than x^{ϵ/(5Co)}. For the ranks under consideration k ≤2x^{9/2+10ϵ}, so, for x ≥16,
log((kx^{26})^{4}) = 4 log k + 104 log x ≤124 log x.
Division by log p > (ϵ/(5C_{o})) log x gives log_{p}((kx^{26})^{4}) ≤620C_{o}/ϵ. The ceiling in each local L_{1}(p) adds at most one, and the definition L_{2} = 2 sup_{p} L_{1}(p) therefore gives exactly the bound in Proposition 3.37. Take P to be the finite set of inert primes below X^{′} whose Frobenius order is at least x^{ϵ/4}, h_{p} their chosen Frobenius elements, and ω_{p} = log p/p. The orbit origin used in the source lies on its orbit by its defining choice. The resulting weighted bound is precisely BadOK, and (69) is Shares(T, x^{−1+ϵ}). This proves the host specialization in ThickFrames/topsBase.lean:79--140 and topsChoiceH.lean:30--67.