Skip to content

Section 3.17 · PDF pages 55–57

The second set and its quantitative size

The notation transcription is provisional. Check it against the printed mathematics when citing or reusing a formula.

3.17 The second set and its quantitative size

Lemma 3.38 (A sphere construction with bounded relations). For integers n ≥0, L ≥2, there is a finite set T ⊂ N such that

Selectable PDF notation • transcription unchecked
_{n} √
4Ls < n (s ∈T), |T| ≥_{L}e^{−32log n log L}.

Here the n = 0 case has lower bound zero. For distinct s_{1}, s_{2}, s_{3} ∈T, one has

Selectable PDF notation • transcription unchecked
j(s_{2} −s_{1}) ̸= i(s_{3} −s_{1}) (0 < |i|, |j| ≤L, i ̸= j, i, j ∈Z) .

Proof. If the stated lower bound is at most one and n > 0, take T = {0}; if n = 0, take the empty set. In the other case write

Selectable PDF notation • transcription unchecked
√ a_{0} −b −3 ⌊ e^{a}⌋

a_{0} = log n, b = log L, s = a_{0}b, S = ⌊s/b⌋, a = , d = , B = 4Ld.

Selectable PDF notation • transcription unchecked
S 4L

The nontrivial case says a_{0} −32s −b > 0. It implies s > 32b, s > 16, S > 31; also b > 1/2. The inequalities Sb ≤s < (S + 1)b give

Selectable PDF notation • transcription unchecked
7 + b ≤a ≤2s, 3 + S(7 + b) + S + 2a ≤32s.

Here are useful direct checks on these scalar steps. Since S ≥ s/(2b), a ≤ a_{0}/S ≤ 2s. For the lower bound it suffices to show s^{2}−b^{2}−3b ≥ 7s + sb, because S ≤ s/b. Use b < s/32 and s > 16 in its left-minus-right side; it is greater than (1 −1/32 −1/1024)s^{2}−(7 + 3/32)s > 0. For the last upper bound, Sb ≤s, S ≤s/b < 2s and a ≤2s bound it by 3 + 21s ≤32s. In particular e^{a}≥8L, so

Selectable PDF notation • transcription unchecked
_{e}a_{e}a
_{8L} ≤d ≤_{4L}, d ≥1.

Consider the d^{S} integer vectors v = (v_{0}, . . . , v_{S−1}) with 0 ≤ v_{i} < d. Their squared lengths have at most Sd^{2} possible integer values. Some sphere 𝒮 = {v :∑_{i}v_{i}^{2}= k} therefore has at least d^{S}/(Sd^{2}) points. Encode them by

Selectable PDF notation • transcription unchecked
S∑−1
F(v) = v_{i}B^{i}, T = F(𝒮).
i=0

The map is injective. Indeed if ∑_{i}c_{i}B^{i} = 0 with integer |c_{i}| < B, reduction modulo B gives c_{0} = 0; division by B repeats the argument. Use c_{i} = v_{i} −w_{i} for injectivity. Also F(v) < B^{S}, and

Selectable PDF notation • transcription unchecked
4LB^{S}≤4Le^{aS}= 4e^{a0−3}≤n.

This proves the required range.

Suppose there were one of the forbidden relations. The same radix argument applies to

Selectable PDF notation • transcription unchecked
c_{m} = j(v_{2,m} −v_{1,m}) −i(v_{3,m} −v_{1,m}), |c_{m}| < 2Ld < B.

Thus j(v_{2} −v_{1}) = i(v_{3} −v_{1}) coordinatewise. Put A = v_{2} −v_{1}, D = v_{3} −v_{1}. Equality of the three squared lengths gives

Selectable PDF notation • transcription unchecked
2⟨v_{1}, A⟩+ ‖A‖^{2}= 0, 2⟨v_{1}, D⟩+ ‖D‖^{2}= 0.

Multiply the first by j^{2}, the second by ij, and subtract, using jA = iD. The result is i(i −j)‖D‖^{2} = 0. Both integer factors are nonzero, so D = 0; then jA = 0 gives A = 0, contradicting distinctness.

Finally the cardinal lower bound has the asserted size. Since e^{aS}= ne^{−3}/L,

Selectable PDF notation • transcription unchecked
n = e^{aS}Le^{3}, e^{aS}≤d^{S}(8L)^{S}, d^{2}≤e^{2a}.

The scalar upper bound already proved implies

Selectable PDF notation • transcription unchecked
_{e}3_{(8L)}S_{Se}2a_{≤e}3+S(7+b)+S+2a_{≤e}32s_{.}

Combining these inequalities yields

Selectable PDF notation • transcription unchecked
_{nd}S
_{L}e^{−32s} ≤_{Sd2} ≤|T|.

This proves the construction and every stated bound. It is the sphere, signed-radix and parameter proof in Formalism/FrobeniusOrbits/FrobeniusOrbitsProofs/ThickExists.lean:11--334. The finite pigeonhole step is also exactly the Behrend.exists_large_sphere used there; no density assertion about a different kind of progression-free set is being substituted.

Proposition 3.39 (The second host set). There is an absolute C_{T2} > 0 such that, for every fixed 0 < ϵ < 1/52, C_{o}, C_{L} > 0, all sufficiently large x, every frame with

o ≤C_{o}, n = on_{0},^{1}_{2}x^{2+8ϵ} ≤n ≤C_{o}x^{2+8ϵ}, 2 ≤L ≤C_{L} log x,

admits a set T_{2} ⊂ N_{>0} with the relation exclusion of Lemma 3.38 and

Selectable PDF notation • transcription unchecked
4La < n_{0} (a ∈_{√}T_{2}), 4L|T_{2}| ≤n_{0},
|T_{2}| ≥^{n}_{L }^{0}e^{−CT 2log n0 log L}, |T_{2}| ≥x^{−ϵ}n.

One may take C_{T2} = 64.

Selectable PDF notation • transcription unchecked
√

Proof. Apply the preceding lemma to n_{0}, L, and delete zero from its set. Put v = log n_{0} log L, E = e^{32v}, Q = n_{0}/(LE). Uniformly under the displayed hypotheses,

Selectable PDF notation • transcription unchecked
_{x}2+8ϵ

≤n_{0} ≤C_{o}x^{2+8ϵ}, log L ≤ log C_{L} + log log x.

Selectable PDF notation • transcription unchecked
√ 2C_{o}

Thus v = O_{ϵ,Co,CL}(log x log log x) = o(log x). It follows, with the constants fixed before x, that E ≥2 and

Selectable PDF notation • transcription unchecked
4C_{o}LE ≤x^{ϵ}, Q ≥4x^{−ϵ}n ≥4

for all sufficiently large x. The deletion loses at most one point, so

Selectable PDF notation • transcription unchecked
|T_{2}| ≥Q −1 ≥Q/4 ≥x^{−ϵ}n, |T_{2}| ≥Q/2 ≥Q/E =^{n}_{L }^{0}e^{−64v}.

The range and relation exclusion pass to a subset. If T_{2} ̸= ∅, its largest member is at least |T_{2}|, since all its members are positive integers; multiplying by 4L proves 4L|T_{2}| ≤n_{0}. The empty case is immediate. This is the deletion and size argument in ThickFrames/ThickFrame2Large.lean:29--198. For the host take

L = L_{w} = 10⌈405 log x⌉+ 2⌈30/ϵ⌉+ 22.

When log x ≥1, ceiling bounds give L_{w} ≤(4084 + 60/ϵ) log x; also L_{w} ≥2. Thus this choice has exactly the required uniform form, as in ShortNorms/hostOfFieldOf.lean:58--95.