ABC: source and evidence reader

Download original file

This is the original TeX manuscript source. Use the paper’s PDF for typeset equations.

Read the typeset paper

1 \clearpage
2 \section{Exact Moving-Coset Search and the First-Order Barrier}
3 
4 \subsection{Obstruction cosets}
5 Exclude $(1,1,2)$ throughout this section. Choose a section $x_0\in L$ with $\omega(x_0)=1$. Then
6 \[
7  L
8  =
9  \bigsqcup_{k\in\Z}
10  (kx_0+L_0).
11 \]
12 For fixed $k$, the problem is a closest-vector problem to the moving target $-kx_0$ in the lattice $L_0$. The three-sector compression makes this search much more explicit.
13 
14 \subsection{Aggregate affine line}
15 Write
16 \[
17  u=P_ur_u,
18  \qquad
19  r_u=\rad(u),
20  \qquad
21  P_u=u/r_u.
22 \]
23 The sharp aggregate conditions are
24 \[
25  P_at_a+P_bt_b=P_ct_c
26 \]
27 and
28 \[
29  r_at_b-r_bt_a=kP_c.
30 \]
31 Since $\gcd(r_a,r_b)=1$, choose $s,t$ with
32 \[
33  sr_a+tr_b=1.
34 \]
35 One solution is
36 \[
37  t_a^{(0)}=-tkP_c,
38  \qquad
39  t_b^{(0)}=skP_c.
40 \]
41 Every aggregate solution is
42 \[
43  \boxed{
44  \begin{aligned}
45  t_a(k,n)&=t_a^{(0)}+nr_a,\\
46  t_b(k,n)&=t_b^{(0)}+nr_b,\\
47  t_c(k,n)&=t_c^{(0)}+nr_c,
48  \end{aligned}
49  \qquad n\in\Z.
50  }
51 \]
52 When $a,b>1$, the global search in one obstruction coset is therefore one-dimensional. If $a=1$, the empty $a$-sector forces $t_a=0$ and fixes the coarse parameter, giving
53 \[
54  (t_a,t_b,t_c)=(0,kP_c,kP_b).
55 \]
56 If $b=1$, the corresponding fixed triple is
57 \[
58  (t_a,t_b,t_c)=(-kP_c,0,-kP_a).
59 \]
60 Thus a unit-sector coset has one aggregate candidate rather than a moving affine line.
61 
62 \subsection{Local CRT normal form}
63 Fix one sector with primes
64 \[
65  p_1,\ldots,p_m
66 \]
67 and radical
68 \[
69  r=\prod_i p_i.
70 \]
71 For a nonempty sector, the local equation is
72 \[
73  \sum_i\frac r{p_i}x_i=t.
74 \]
75 An empty unit sector has no prime coordinates and is feasible exactly when $t=0$.
76 Modulo $p_i$, the coordinate $x_i$ is forced:
77 \[
78  x_i
79  \equiv
80  t\left(\frac r{p_i}\right)^{-1}
81  \pmod{p_i}.
82 \]
83 Choose the centered residue $\xi_i$ and write
84 \[
85  x_i=\xi_i+p_i z_i.
86 \]
87 Substitution gives one quotient equation
88 \[
89  \sum_i z_i=q(t).
90 \]
91 For a box radius $H$, each $z_i$ lies in the interval
92 \[
93  \ell_i(H)
94  =
95  \left\lceil\frac{-H-\xi_i}{p_i}\right\rceil
96  \le z_i\le
97  \left\lfloor\frac{H-\xi_i}{p_i}\right\rfloor
98  =u_i(H).
99 \]
100 The local lift exists exactly when
101 \[
102  \boxed{
103  \ell_i(H)\le u_i(H)\ \text{for every }i,\qquad
104  \sum_i\ell_i(H)\le q(t)\le\sum_i u_i(H).
105  }
106 \]
107 Every coordinate interval must be nonempty. Once that condition holds, the sum of the integer intervals contains every integer between the sums of their endpoints. This proves the criterion. Summing endpoints alone is insufficient when one interval is empty.
108 
109 \subsection{Moving-interval theorem}
110 Using the complete local criterion, including the individual nonemptiness guards, for fixed $k$ and $H$ the three sectors produce three integer intervals for the coarse parameter $n$. A packet of height at most $H$ exists if and only if those intervals share an integer.
111 
112 \begin{theorem}[Moving-interval theorem]
113 For fixed obstruction multiple $k$ and radius $H$,
114 \[
115  H(k)\le H
116 \]
117 if and only if
118 \[
119  I_a(H,k)
120  \cap
121  I_b(H,k)
122  \cap
123  I_c(H,k)
124  \cap\Z
125  \neq\varnothing.
126 \]
127 \end{theorem}
128 
129 The first feasible $H$ gives the exact coset height. The preceding radius is an explicit no-smaller-box certificate.
130 
131 \subsection{Finite global stopping}
132 The continuous lower bound gives
133 \[
134  H(k)\ge k\overline H.
135 \]
136 If the best exact height found so far is $B$, then no coset with
137 \[
138  k\overline H\ge B
139 \]
140 can improve it. Therefore only finitely many obstruction multiples must be searched:
141 \[
142  \boxed{
143  1\le k\le
144  \left\lfloor\frac{B-1}{\overline H}\right\rfloor.
145  }
146 \]
147 Every unsearched coset is excluded by a proved lower bound.
148 
149 \subsection{Phase and coarse separation}
150 The local target has the form
151 \[
152  t_u(k,n)=\alpha_uk+r_un.
153 \]
154 For a local prime $p\mid r_u$,
155 \[
156  t_u(k,n)\equiv\alpha_uk\pmod p.
157 \]
158 Thus the obstruction multiple $k$ determines the finite phase packet. The coarse parameter $n$ changes only the quotient load. The exact search is a moving polyphase mechanism rather than a generic mixed-integer program.
159 
160 \subsection{Arithmetic correction and arbitrary precision}
161 Some large high-quality triples exceed signed $64$-bit range, and intermediate quantities such as
162 \[
163  ab,
164  \qquad
165  \frac{abc}{R},
166  \qquad
167  w\cdot x
168 \]
169 can overflow even when the input terms individually fit. Every public arithmetic entry point must therefore promote integer-like inputs to arbitrary-precision integers before multiplication. Floating-point values are display-only. All logical comparisons and stopping bounds are exact rational or integer computations.
170 
171 Several reported ratios are mathematically at least one:
172 \[
173  \frac{\Phi}{\overline H}\ge1,
174  \qquad
175  \frac{\Phi}{k_*\overline H}\ge1,
176  \qquad
177  \frac{H(1)}{\Phi}\ge1.
178 \]
179 Values above one are not probability errors.
180 
181 \subsection{What the exact search proved}
182 The moving search found nonprimitive optima on many finite examples. It also found increasingly deep phase resonances. This showed that a fixed cutoff in $k$ is unjustified. More importantly, the no-escape identity proved that even a complete exact search of the first-order invariant cannot imply $abc$ independently. The search became a diagnostic and classification engine rather than the final proof mechanism.

Back to source controls

Back to ABC: source and evidence reader