f0945ea 29d65c0
SINGLE-FOLD DIOPHANTINE REPRESENTATIONS
Second edition, rewritten for a first-time reader.
This document is the complete proof of a single theorem (plus
one corollary):
Every recursively enumerable subset of N^n is Diophantine with
exactly one complete auxiliary tuple for each member.
That is the "single-fold conjecture" over the natural numbers, and
it implies the older "finite-fold conjecture".
How to read this document.
The proof has two halves, and the boundary between them is Section 7.
The first half is "arithmetic": it builds a single, very particular
integer-valued function g : N -> N whose graph is single-fold, and
whose logarithm sits strictly between delta*(log u)^2 and u*log u for
some fixed delta > 0 and all large u. To do this we need a supply of
uniquely coded rational numbers arranged as the rational points of
the elliptic curve E : y^2 = x^3 - 25x. Sections 3-6 set up the
codes and heights.
The second half is "logic": Sections 7-9 use g to build a
single-fold relation Pow(b,n,c) meaning "b >= 2 and c = b^n", then
a single-fold relation x << y meaning "the 1-bits of x are a
subset of the 1-bits of y", then encode an entire halting computation
of a small machine into polynomial equations. Section 10 collapses
all of that into the single polynomial of Theorem 1.
The one idea to keep in mind throughout: we do not merely want "the
polynomial has a solution iff a is in S"; we want "there is exactly
one complete tuple of solutions". Almost every bookkeeping choice
below is forced by that. The most common failure mode is that a
subproblem has many solutions, and we keep asking (in each lemma)
whether ours has exactly one.
Every section stands on its own; no result from outside is assumed,
though some familiar theorems (Mordell-Weil, Nagell-Lutz, the
canonical height theorem) are quoted by name when they are not the
point of the section. Where such a theorem is used, only the exact
statement needed is stated; the reader who wants proofs may consult
Silverman's "Arithmetic of Elliptic Curves" for those.
Notation. N = {0, 1, 2, ...}, so 0 is a natural number. Z, Q are
integers and rationals. For a real number x we write log x for its
natural logarithm. For an integer a >= 2 and n >= 0 we write b^n
for the ordinary power.
------------------------------------------------------------------------
1. THE MAIN THEOREM.
------------------------------------------------------------------------
For x, y in N, write x << y to mean: every binary digit of x that is
1 is also 1 in the binary expansion of y. Equivalently, writing
x = sum_i x_i 2^i and y = sum_i y_i 2^i with x_i, y_i in {0,1},
we have x_i <= y_i for every i. Note x << y implies x <= y. We will
call this "binary containment".
For b, n, c in N write Pow(b, n, c) for the relation:
b >= 2 and c = b^n.
A Diophantine representation of S, a subset of N^n, is an integer
polynomial
P in Z[A_1, ..., A_n, W_1, ..., W_m]
such that for every a in N^n:
a in S <=> there is w in N^m with P(a, w) = 0.
The representation is single-fold if the tuple w is unique whenever
it exists. It is finite-fold if the set of such w is finite for each
a. Note that a polynomial P exists but its degree, its number of
variables, and its coefficients are not displayed.
Theorem 1 (main). For every n >= 1 and every recursively enumerable
set S <= N^n there exist m >= 1 and P in Z[A_1, ..., A_n, W_1, ...,
W_m] such that for every a in N^n,
#{ w in N^m : P(a, w) = 0 } = 1 if a in S,
0 if a not in S.
Corollary 2. There exist integers m, D >= 1 with the following
property. No algorithm has this behaviour: on every input polynomial
F in Z[W_1, ..., W_m] of total degree at most D satisfying the
promise
#{ w in N^m : F(w) = 0 } <= 1,
the algorithm halts and correctly decides whether that set is empty.
What "recursively enumerable" means. A set S <= N^n is recursively
enumerable iff some deterministic machine, given (a_1, ..., a_n),
halts on exactly the members of S and runs forever on the rest.
This is the only machine property we will use from S. We will be
free to choose a convenient machine.
A very short history. Davis, Putnam and Robinson proved that every
recursively enumerable relation is "exponentially Diophantine":
allows exponentiation as a primitive. Matiyasevich (1970) proved
that in fact every such relation is Diophantine, settling Hilbert's
tenth problem negatively. Matiyasevich (1974) proved that every
such relation has a single-fold exponential representation.
Closing the gap to single-fold polynomial representation is exactly
what Theorem 1 accomplishes. See the references at the end.
Proof outline.
Section 2 fixes the "witness bookkeeping": how to combine
single-fold systems by conjunction, composition, and disjoint
cases, and how to count their auxiliary variables once and for all.
This section is technical but essential; every later argument
will say "by Section 2" instead of re-verifying bookkeeping.
Section 3 gives exact one-to-one codes for rational numbers and
for points of the curve E : y^2 = x^3 - 25x, together with a
single-fold implementation of addition on E.
Section 4 determines the group E(Q): it is generated by one point
of infinite order together with the four-point torsion subgroup
T = { O, (0,0), (5,0), (-5,0) }. Every rational point Q of E
is thus uniquely nP + t with n in Z and t in T.
Section 5 uses the Neron-Tate height to turn "index n" into "size
of a specific integer". It builds the function g with the two
bounds delta (log u)^2 < log g(u) < u log u.
Section 6 proves the classical Pell-sequence facts: every positive
solution of x^2 - (a^2-1) y^2 = 1 is a Pell solution (x_i, y_i),
with x_i, y_i increasing rapidly, y_i congruent to i mod (a-1),
and ratios y_{n+1}(bu)/y_{n+1}(u) close to b^n.
Section 7 uses the lower bound on g to force the appropriate Pell
solutions to fit beneath a fixed integer v = g(u), and then uses
the upper bound to force their indices to be exactly n+1 by a
congruence. The output c = b^n is then recovered as an integer
quotient with error strictly < 1.
Section 8 uses Pow and Lucas's parity criterion for binomial
coefficients to get a single-fold representation of x << y.
Section 9 encodes a halting run of a counter machine. It uses the
classical large-base trick of Jones and Matiyasevich, and a "clock"
that forces the base to be a power of two. Binary containment then
says which digits are permitted, and the polynomial identities
enforce transitions. The encoding is single-fold because a
deterministic machine has exactly one run.
Section 10 collects: substitute every single-fold sub-system into
the machine system and take the sum of squares of the equations.
Section 11 proves Corollary 2 from Theorem 1.
Appendix A spells out in detail every coordinate that the uniqueness
claim covers, so that "single-fold" can be checked literally.
References.
------------------------------------------------------------------------
2. BOOKKEEPING: KEEPING UNIQUENESS UNDER COMPOSITION.
------------------------------------------------------------------------
All later constructions are made by gluing small polynomial systems
together. A "single-fold" small system has exactly one solution
tuple for each qualified input; when we glue, we must not accidentally
create extra solutions. This section makes that rule explicit and
will be invoked by number in every later section, so the reader can
skip the details on first reading and come back when a uniqueness
claim seems dubious.
Definition 3. A single-fold polynomial system for a relation
R <= N^d is a finite list of integer polynomial equations
F_1(a, z) = 0, F_2(a, z) = 0, ..., F_N(a, z) = 0
with a in N^d and z in N^k, and with the property: for each a in N^d,
the set of z satisfying all F_i(a, z) = 0 is a single point if a is
in R, and is empty if a is not in R. A single-fold graph of a
function f : D -> N^e (D <= N^d) is such a system for the graph
{(a, f(a)) : a in D}; so for a in D both f(a) and every other
coordinate are unique.
Sign and slack conventions. These are used throughout.
(S1) Every variable in every system ranges over N; there are no
integer values, only natural ones. Negative numbers are
handled by signs, see (S5).
(S2) A polynomial may have negative coefficients. The equation
F(a,z) = 0 still makes sense.
(S3) A displayed inequality F >= G is shorthand for F - G = s
with a fresh variable s in N. Because s is uniquely
determined (as the nonnegative value F-G), this adds exactly
one coordinate and never creates ambiguity. Similarly, a
strict inequality F > G is F - G = 1 + s for a fresh s.
(S4) To "name" a polynomial expression E as a natural-number
variable, introduce a fresh variable e and impose e = E.
Again, one coordinate, exactly determined by E.
(S5) To represent a possibly negative integer z, use the unique
sign split z = z^+ - z^- with z^+, z^- in N and
z^+ * z^- = 0. Then |z| = z^+ + z^-. This split is
single-fold (for z = 0, both parts are 0; for z > 0 only
z^+ is nonzero; for z < 0 only z^- is).
(S6) A finite system F_1 = 0, ..., F_N = 0 is equivalent, over
N, to the single equation F_1^2 + ... + F_N^2 = 0. This
substitution changes no variables and no solutions. It is
how the polynomial of Theorem 1 will be manufactured at the
end.
Lemma 4 (composition of single-fold systems). Single-fold systems
combine in the following three ways.
(a) CONJUNCTION. If R_1, ..., R_t each have single-fold systems
on the same argument tuple a, in pairwise-disjoint auxiliary
tuples, then the intersection R_1 ∩ ... ∩ R_t has a single-
fold system: place the systems side by side. The full tuple
is unique iff every coordinate of every system is unique.
(b) COMPOSITION. If f : D -> N^e has a single-fold graph and
h : E -> N^k has a single-fold graph with f(D) <= E, then
the graph of h(f(a)) has a single-fold system: substitute
f(a) for the first argument of the second system, using
(S4) to name the intermediate tuple.
(c) DISJOINT UNION. If R_1, ..., R_t are single-fold relations
on the same argument tuple and their argument sets are
pairwise disjoint, then the union R_1 ∪ ... ∪ R_t is
single-fold.
Proof. Parts (a) and (b) are immediate: each successive step is
uniquely determined by the previous one, and no two steps share a
coordinate.
The only subtle point is (c). Introduce Boolean selectors e_1, ...,
e_t in N with
e_i (e_i - 1) = 0 for every i
e_1 + ... + e_t = 1
So exactly one e_i equals one and the rest are zero. Inside each
case i, multiply every polynomial equation - guards, base equations,
all coordinates and slacks declared inside case i, including
coordinates of the deeper calls used by case i - by e_i. Separately,
for every variable z that is "local" to case i (i.e. declared only
inside its system, not a shared argument or a shared output of the
whole union), impose
(1 - e_i) z = 0.
Now take an argument a in R_i for exactly one i (disjointness). Set
e_i = 1; other e_j = 0. Then all equations of case i are unchanged,
so they have the single witness tuple for a in R_i, plus all slacks
and intermediate coordinates. For j ≠ i, all local variables of case
j are forced to zero. The two shared coordinates that could still
be "free" are the shared output; but the shared output is required
to be a piece of case i's sole witness, and every other case is
switched off. So the whole tuple is unique. Conversely if a is in no
R_i, then for each i, e_i = 1 forces the equations of case i, which
have no solution; so no selector can equal 1, contradicting
e_1 + ... + e_t = 1. So the union has no solution. This finishes the
proof. []
Two remarks on Lemma 4. (i) In (c), the "shared output" is the same
variable across all cases; only one case produces a value for it in
any solution. If a sub-call inside a case wants an output coordinate
with the same name as the top-level output, we use a fresh variable
for the sub-call and impose a defining equality; that keeps
"inactive local variables" clearly separated. (ii) We never use a
slack variable of case i to name anything that case j depends on.
The rule we will follow in what follows. Every time we implement a
function by cases, we will check:
- the guards partition the domain (every valid input satisfies
exactly one guard);
- each active case determines the output (and every other shared
value) uniquely;
- all other coordinates, including slacks and further local
variables, are single-fold once the case is chosen.
In this way, the union is single-fold as a whole.
Location and slack conventions. In the systems below, an integer
that is known nonnegative is used directly; an integer that may be
negative uses the split (S5). A quotient with a positive divisor is
always specified as "a = d q + r with r < d", both and the slack
unique. A Bezout coefficient is never mentioned; coprimality of
rational numbers will be handled inside the rational code below
(Section 3) without ever writing down a Bezout coefficient.
------------------------------------------------------------------------
3. RATIONAL CODES AND POINT CODES FOR E : y^2 = x^3 - 25x.
------------------------------------------------------------------------
This section does two things. First, it gives a polynomial system
that codes each element of Q by a single 6-tuple of naturals, with a
matching polynomial arithmetic. Second, it uses that to code each
rational point of E, and it implements the group law on E with a
single-fold system.
3a. Rational codes.
Definition 5. A rational code is a 6-tuple (p, n, d, t, s, q) in
N^6 satisfying three equations:
(R1) p * n = 0
(R2) d = 1 + t + s
(R3) (p + n) * t + d = 1 + q * d
The rational number represented by this code is (p - n) / d.
Lemma 6 (rational codes are unique). Every element of Q has exactly
one rational code. In particular, the code of an integer m is the
tuple (p, n, 1, 0, 0, 0) where p = max(m,0) and n = max(-m,0).
Proof. Let a = p + n. Equation (R3) rearranges to at = (q-1)d + 1,
so at is congruent to 1 modulo d; in particular gcd(a, d) = 1 and, by
(R1), gcd(p - n, d) = gcd(a, d) = 1. So p - n and d are coprime,
i.e. the fraction (p-n)/d is in lowest terms.
Conversely, take a fraction r = A/B with A in Z, B >= 1,
gcd(A, B) = 1. Set p = max(A, 0) and n = max(-A, 0). Then p+n = |A|
and p-n = A, and pn = 0. Equation (R2) forces s = d - 1 - t, which
is a nonnegative integer iff 0 <= t <= d - 1; the choice of t in
[0, d-1] uniquely determines s. Equation (R3) requires
(p+n)t = (q-1)d + 1, which is equivalent to
(p+n) t = 1 (mod d).
Since gcd(p+n, d) = gcd(|A|, B) = 1, this congruence has exactly
one solution t in [0, d - 1]. That fixes t; then s = d - 1 - t and
q = ((p+n)t + d - 1) / d are forced. For d = 1, the only solution
is t = s = q = 0. Therefore every fraction has at most one code; and
the construction just given shows that it has at least one. Hence
exactly one. []
Integers in canonical code. Every integer m has code
(p, n, 1, 0, 0, 0) with p = max(m,0), n = max(-m,0). Fix this once
and for all.
Rational arithmetic. Every fixed rational expression in some
inputs, with nonzero prescribed denominators, becomes a polynomial
system. As an example, if rationals with codes (p_i, n_i, d_i, ...)
for i = 1, 2, 3 satisfy z_1 + z_2 = z_3, then
(p_1 - n_1) d_2 d_3 + (p_2 - n_2) d_1 d_3
= (p_3 - n_3) d_1 d_2,
which is a polynomial equation in the code coordinates alone.
Similarly, z_1 * z_2 = z_3 becomes
(p_1 - n_1) (p_2 - n_2) d_3 = (p_3 - n_3) d_1 d_2,
and a comparison z_1 <= z_2 becomes
(p_1 - n_1) d_2 <= (p_2 - n_2) d_1 after clearing positive
denominators. New rational outputs are declared as their own
6-coordinate code with (R1)-(R3) imposed. Since the value is unique
and rational codes are unique, the whole output code is unique.
Lemma 7 (rational arithmetic is single-fold). Any fixed finite
sequence of rational additions, multiplications, divisions by
nonzero divisors, and comparisons on valid codes has a single-fold
polynomial implementation with unique outputs and auxiliary
coordinates.
Proof. Follows from Lemma 6 and Lemma 4(b). []
3b. Point codes on E.
The curve. Let E be the projective closure of
y^2 = x^3 - 25 x.
The point at infinity is O = [0:1:0]. With the chord-tangent law E
is a group with identity O; negation is (x, y) |-> (x, -y).
Point code. A point code for a rational point Q of E is a tuple
(o, code_x, code_y)
where o in {0,1} is a "flag" and code_x, code_y are rational codes.
The reading rule:
- if o = 1, then Q = O, and we require both numerators of code_x
and of code_y to be zero. (Both rational parts are then the
canonical code (0,0,1,0,0,0) of zero, so uniqueness is
automatic.)
- if o = 0, then code_x represents x(Q), code_y represents y(Q),
and the curve equation is imposed:
a_y^2 d_x^3 = d_y^2 (a_x^3 - 25 a_x d_x^2),
where a_x = p_x - n_x, d_x is the denominator of code_x, and
similarly a_y, d_y. (This is y^2 = x^3 - 25x multiplied by
d_y^2 d_x^3.) The o = 0 branch leaves x, y free (subject only
to the curve equation); it places no constraint linking x, y
to (0, 0) or to any particular point.
So the o = 1 branch codes exactly O, and the o = 0 branch codes
exactly the affine points {(x, y) : y^2 = x^3 - 25x}. Because the
two branches impose contradictory numerator conditions (o = 1 forces
both numerators to zero, which for the affine branch (o = 0) is
exactly the single point (0,0) - different point but different
flag), the codes are distinguished.
Every rational point of E has exactly one point code. Indeed: for
Q = O, the answer is o = 1 and the canonical zero codes; for
Q = (x, y) affine, the answer is o = 0 with the unique rational
codes of x and y, which satisfy the curve equation by the
construction of Q.
3c. Addition on E, as a single-fold system.
Given valid point codes for Q_1, Q_2 in E(Q), we implement Q_3 =
Q_1 + Q_2 by seven cases. Each case is defined on the underlying
rationals of x(Q_1), y(Q_1), x(Q_2), y(Q_2). The seven cases:
1. Q_1 = O. Output Q_3 = Q_2. (Only code_y, code_x of Q_2
are copied; flag o_3 = o_2.)
2. Q_1 ≠ O, Q_2 = O. Output Q_3 = Q_1.
3. Both affine, x_1 < x_2.
4. Both affine, x_1 > x_2.
5. Both affine, x_1 = x_2, y_1 + y_2 = 0. Output Q_3 = O.
6. Both affine, x_1 = x_2, y_1 = y_2 > 0.
7. Both affine, x_1 = x_2, y_1 = y_2 < 0.
Disjointness and exhaustiveness. For affine points with x_1 = x_2,
the curve equation gives y_1^2 = y_2^2, so y_1 = y_2 or y_1 = -y_2.
If y_1 = -y_2 (case 5), output O. If y_1 = y_2 and nonzero, then
either y_1 = y_2 > 0 (case 6) or y_1 = y_2 < 0 (case 7). If
y_1 = y_2 = 0, then y_1 + y_2 = 0, so case 5. Thus the seven cases
cover all possibilities and are pairwise disjoint. For the Q_1 = O
case, the flag disambiguates; the case "Q_1 ≠ O, Q_2 = O" is
similarly flagged. No case overlaps another.
Case-by-case computations.
Cases 3 and 4 (x_1 ≠ x_2). Introduce a local rational code for
the slope λ and impose
λ (x_2 - x_1) = y_2 - y_1.
Since x_2 - x_1 ≠ 0, λ is uniquely determined. The output is
affine:
x_3 = λ^2 - x_1 - x_2
y_3 = λ (x_1 - x_3) - y_1.
These are the chord formulas. The output code is a fresh valid
rational code.
Cases 6 and 7 (x_1 = x_2, y_1 = y_2 ≠ 0). Same form, with local
slope
λ (2 y_1) = 3 x_1^2 - 25.
Since y_1 ≠ 0, λ is uniquely determined. The output is affine:
x_3 = λ^2 - 2 x_1
y_3 = λ (x_1 - x_3) - y_1.
This is the tangent formula.
Cases 1 and 2 output the other point (with o_3 = o_2 or o_1)
directly.
Case 5 outputs O: take the canonical code o = 1 with both
numerator parts zero. Unique.
All rational operations in each case are single-fold by Lemma 7.
The disjoint-case bookkeeping (Lemma 4(c)) then makes the whole
addition single-fold.
Lemma 8 (point addition is single-fold). Given valid point codes for
Q_1, Q_2 in E(Q), the addition Q_3 = Q_1 + Q_2 has a single-fold
polynomial implementation with a unique output point code and a
unique full tuple of auxiliary coordinates.
Proof. Combine the seven cases with Lemma 4(c). Each case is
single-fold as a finite conjunction of single-fold systems by
Lemmas 4(a) and 7: point addition sets a fresh output code once the
inputs and the local slope are determined, and the slope is unique.
The disjoint-case construction of Lemma 4 handles "one of seven". []
Repetition. By Lemma 4(b), any fixed finite chain of additions, and
multiplication by any fixed positive integer m_*, has a single-fold
system: pick an addition chain m_* = a_1 + a_2 + ... + a_k with
a_i fixed positive integers whose sum equals m_*, and iterate
Lemma 8. Nothing in the argument depends on how many additions the
chain has. We fix one such chain once and for all in Section 5.
We henceforth regard E as equipped with its unique point codes, its
single-fold addition, and its unique multiplication by any fixed
positive integer. Fixed rational points are inserted by their
integer codes: for example, P, and the four torsion points
O, (0,0), (5,0), (-5,0), all have fixed codes. No assertion is made
that a computer can discover them; existence is enough.
------------------------------------------------------------------------
4. THE RATIONAL POINTS OF E.
------------------------------------------------------------------------
This section determines the abstract group E(Q). The answer is
needed twice. First, we need to know that the group is generated by
one point P of infinite order together with its four-element torsion
subgroup T; that lets us index rational points by an integer. Second,
we need to know exactly what T is, so that Section 5 can pick a
"canonical representative" of each coset nP + T.
Proposition 9. For E : y^2 = x^3 - 25x,
E(Q) = Z * P (+) T
where P is a point of infinite order (obtained from (-4, 6)) and
T = { O, (0, 0), (5, 0), (-5, 0) } = Z/2 x Z/2.
In particular, every rational point of E has a unique expression
nP + t with n in Z and t in T.
The proof is a two-isogeny 2-descent, following Silverman's exposition;
we write out the parts that will be reused in later sections.
General two-isogeny descent. For a, b in Q with b(a^2 - 4b) ≠ 0, set
E_{a,b} : y^2 = x^3 + a x^2 + b x,
b' = a^2 - 4 b,
E' = E_{-2a, b'}.
Then E_{a,b} and E' are nonsingular elliptic curves and there are
mutually dual isogenies
φ : E_{a,b} -> E', φ(x, y) = ( y^2/x^2, y(1 - b/x^2) ),
ψ : E' -> E_{a,b}, ψ(X, Y) = ( Y^2/(4X^2), (Y/8)(1 - b'/X^2) ),
with O and the 2-torsion point (0, 0) sent to O under each. One
checks by direct substitution that subtracting the two equations
yields the target equation. (The reader is welcome to specialise to
a = 0, b = -25 and check with a CAS.) The maps are group
homomorphisms because they are nonconstant morphisms preserving the
identity.
Square-class homomorphism. Write [c] for the class of c in Q* modulo
squares. Define
α : E_{a,b}(Q) -> Q* / (Q*)^2,
α(O) = [1],
α((0,0)) = [b],
α((x, y)) = [x] for x ≠ 0.
A calculation with the chord-tangent intersection product shows α is
a homomorphism: for three collinear points Q_1, Q_2, Q_3 the product
of α values is trivial; the same identity holds for a tangent line
using multiplicity, and for vertical lines because -Q has the same
x-coordinate as Q. Compare Silverman III.4.8 and X.4.8.
Two facts we will use repeatedly (Silverman III.4.5 and X.4.9):
ker α = ψ ( E'(Q) ) (as subgroups of E_{a,b}(Q))
ker α' = φ ( E_{a,b}(Q) ) (as subgroups of E'(Q))
where α' is the analogous square-class map on E'.
The composition ψφ of ψ with φ equals 2 on E_{a,b}, up to sign
(this is standard: for (x,y) with xy ≠ 0, the x-coordinate of
ψ(φ(x,y)) is (x^2 - b)^2 / (4 y^2) which equals x(2Q), see
Silverman III.4.8). Hence ψ E'(Q) contains 2 E_{a,b}(Q). Combined
with ker α = ψ E'(Q) and the analogous relation on E', the maps
induce short exact sequences of finite 2-groups
0 -> E_{a,b}(Q) / ψ E'(Q) -> Q*/(Q*)^2
0 -> E'(Q) / φ E_{a,b}(Q) -> Q*/(Q*)^2
so
[E_{a,b}(Q) : 2 E_{a,b}(Q)]
= | im α | * | im α' |.
This is the two-isogeny descent.
Specialisation. Set a = 0, b = -25. Then
E = E_{0,-25} : y^2 = x^3 - 25x,
E' = E_{0,100} : y^2 = x^3 + 100x.
Valuation arguments. Let p be a prime. Suppose Q = (x, y) has x ≠ 0
and y ≠ 0. Then v_p(x^2 + a x + b) agrees with v_p(b) when p is
odd and p does not divide b; and it is a unit at p when p is a unit
and p ∤ b. Consequently:
for every prime p not dividing b, v_p(x) is even.
So the square class [x] lies in the subgroup generated by the square
classes of the primes dividing b, together with [-1].
Applying to E (b = -25): the only prime dividing |b| is 5. So
im α ⊆ { [1], [-1], [5], [-5] }. These form a subgroup of (Z/2)^2
in Q*/(Q*)^2, of size at most 4. In particular, | im α | ≤ 4.
Applying to E' (b = +100 = 4 * 25): primes dividing 100 are 2 and 5,
and on E' the x-coordinate is positive whenever the point is affine
(y^2 = x(x^2 + 100) forces x > 0). So
im α' ⊆ { [1], [2], [5], [10] }.
These form a subgroup of Q*/(Q*)^2 isomorphic to (Z/2)^2, size 4.
Claim: [2] is NOT in im α'.
Proof. Suppose, for contradiction, that [2] is in im α'. Then there
are integers m, e with gcd(m, e) = 1, e ≠ 0, and
x = 2 m^2 / e^2 with (x, y) in E'(Q).
Substituting y^2 = x^3 + 100 x and clearing denominators gives
(y e^3 / (2 m))^2 = 2 m^4 + 50 e^4.
The right-hand side is an integer; a rational whose square is an
integer is an integer, so 2 m^4 + 50 e^4 = N^2 for some integer N.
Reducing modulo 5: 2 m^4 ≡ N^2 (mod 5). If 5 does not divide m,
then m^4 ≡ 1 (mod 5), so 2 ≡ N^2 (mod 5), but 2 is not a square
modulo 5 (the squares mod 5 are 0, 1, 4). Contradiction. So 5 | m.
Then N^2 ≡ 0 (mod 5) and 5 | N. Write m = 5 m_1 and N = 5 N_1.
The equation becomes
50 m_1^4 + 2 e^4 = N_1^2.
Reducing modulo 5 again: 2 e^4 ≡ N_1^2 (mod 5). If 5 does not
divide e, we again get 2 ≡ N_1^2 (mod 5), contradiction. So 5 | e.
But then 5 divides both m and e, contradicting gcd(m,e) = 1. Done. [ ]
Index bound. From | im α | ≤ 4 and | im α' | ≤ 2 (since im α' is a
subgroup of a group of order 4 that omits [2], and [2] is the only
generator of order 2 aside from [10] = [2][5] - containment yields
| im α' | ≤ 2), we get
[E(Q) : 2 E(Q)] ≤ 8.
Rank. By Mordell-Weil (quoted) E(Q) is a finitely generated abelian
group; write it as Z^r (+) T. Then 2E(Q) = 2Z^r (+) 2T and
[E(Q) : 2E(Q)] = 2^r * |T[2]| = 2^{r + dim T[2]}.
The 2-torsion T[2] of E is the set of points of order dividing 2,
which on the curve y^2 = x(x^2 - 25) is precisely
{ O, (0,0), (5,0), (-5,0) }.
So dim T[2] = 2 and [E:2E] = 2^{r+2} ≤ 8, hence r ≤ 1.
Positivity of r. The point (-4, 6) lies on E: 36 = -64 + 100. By
Nagell-Lutz, a rational torsion point of a short-Weierstrass integral
model has integer coordinates and either 2Q = O or y(Q)^2 divides
4A^3 + 27B^2 = 4(-25)^3 + 27 * 0 = -62500. Here y(-4,6)^2 = 36, and
36 does not divide 62500 (since 9 does not divide 2^2 * 5^6). Also
2(-4,6) ≠ O because y = 6 ≠ 0. So (-4, 6) is not torsion, so
r >= 1. Hence r = 1.
Torsion. Nagell-Lutz gives integer coordinates for any affine
torsion point of E. Reducing the curve equation modulo 3:
y^2 ≡ x^3 - 25x ≡ x^3 - x ≡ x(x-1)(x+1) ≡ 0 (mod 3), so 3 | y for
any integral point. If y ≠ 0, then 9 | y^2 and (Nagell-Lutz)
y^2 divides 62500 = 4*5^6, which has no factor of 3, contradiction.
Hence every affine torsion point has y = 0, and the affine zeroes
of x^3 - 25x = x(x-5)(x+5) are (0,0), (5,0), (-5,0). Combined with
O, this is T = { O, (0,0), (5,0), (-5,0) }.
Choice of P. The group E(Q)/T is infinite cyclic since E has rank 1
and T is finite. Choose any point P whose image generates that
quotient. Then every Q in E(Q) has a unique expression Q = nP + t
with n in Z and t in T. This finishes Proposition 9. []
------------------------------------------------------------------------
5. HEIGHTS AND THE GROWTH FUNCTION g.
------------------------------------------------------------------------
This section builds the function g : N -> N whose graph is single-fold
and whose logarithm grows between delta (log u)^2 and u log u. The
single extra ingredient is a canonical height on E(Q), which measures
"how big the x-coordinate of a point is" in a quadratic manner.
5a. The naive height and the canonical height.
Definition 10 (naive height). For a rational number a/d with d > 0
and gcd(a, d) = 1, define
H(a/d) = max( |a|, d ).
For a rational point Q of E set
h_x(Q) = log H( x(Q) ) if Q ≠ O,
h_x(O) = 0.
Theorem 11 (Neron-Tate canonical height). There is a function
hhat : E(Q) -> R_{>=0} with these properties:
(C1) The limit hhat(Q) = (1/2) lim_{N -> infinity} 4^{-N} h_x([2^N] Q)
exists for every Q in E(Q).
(C2) hhat(Q) = 0 iff Q is torsion.
(C3) hhat([j]Q) = j^2 hhat(Q) for every integer j.
(C4) There is a constant c_E > 0, depending on E and on the
x-coordinate, such that for every Q in E(Q) with Q ≠ O,
| h_x(Q) - 2 hhat(Q) | <= c_E.
Proof. See Silverman, Arithmetic of Elliptic Curves, VIII.9.1 (C4),
VIII.9.3 (C3 and C1), and VIII.9.10 (C2). []
The point of this section is exactly (C3) and (C4): the canonical
height of jP is quadratic in j, while the naive height differs from
it by at most c_E uniformly. So although h_x(nP) is not exactly
quadratic in n, it is quadratic up to a bounded error. That bounded
error is what will let us identify n exactly by comparing integers.
We fix, once and for all:
- the generator P of E(Q)/T from Proposition 9;
- the integer kappa with kappa > e^{6 c_E};
- an even positive integer m_* large enough that
a_E := 2 m_*^2 hhat(P)
satisfies
a_E > 2 c_E
and 2 a_E - 6 c_E > log kappa.
Such an m_* exists because hhat(P) > 0 by (C2) applied to the
nontorsion point P. Because m_* is even, [m_*] kills the torsion:
[m_*](t) = O for every t in T.
5b. The function W on E(Q).
For Q in E(Q), define
W(Q) = H( x([m_*]Q) ) if [m_*]Q ≠ O,
W(Q) = 1 if [m_*]Q = O.
W(Q) is a positive integer, is single-fold computable from the point
code of Q (using Lemma 8 for the scalar multiplication and the unique
maximum of |numerator| and denominator in the x-coordinate code), and
only depends on the index |n| in the decomposition Q = nP + t of
Proposition 9. The latter is because [m_*] kills T:
W(nP + t) = W([m_*](nP + t)) = W([m_*]nP) = W(nP).
Define W_j := W(jP) for j >= 0. Note W_0 = 1 (because [m_*]O = O).
For j >= 1:
log W_j = log H( x([m_*] (jP)) ) = h_x([m_*] jP),
by (C3) this equals 2 hhat([m_*] jP) + eps_j for |eps_j| ≤ c_E,
and since hhat is quadratic,
2 hhat([m_*] jP) = 2 m_*^2 j^2 hhat(P) = a_E j^2.
So the exact statement is
log W_j = a_E j^2 + eps_j with |eps_j| <= c_E,
for j >= 1,
W_0 = 1.
Consequently:
W_1 = exp(a_E + eps_1) >= exp(a_E - c_E) > exp(c_E) > 1.
For every j >= 1,
log(W_{j+1}) - log(W_j)
= a_E (2j + 1) + (eps_{j+1} - eps_j)
>= a_E (2j+1) - 2 c_E
> 0 (in fact >= a_E * 3 - 2c_E > 0).
So (W_j)_{j>=0} is strictly increasing and unbounded.
5c. Representatives: one per coset pair.
For each integer j >= 1 we want to single out one canonical point in
the coset pair (jP + T) ∪ (-jP + T). The point will be defined
by height comparisons alone, so it becomes a single-fold existence
statement.
Definition 12 (representative). A point Q in E(Q) is a
representative if all five of
(P1) Q ≠ O,
(P2) y(Q) >= 0,
(P3) W(Q) > 1,
(P4) Q + t ≠ O for every t in T,
(P5) x(Q) >= x(Q + t) for every t in T.
Condition (P5) is a finite conjunction of four comparisons of
rational numbers; (P4) is a finite conjunction of four nontriviality
conditions; (P2) is a single comparison; (P3) is a single
comparison. Every clause is a polynomial relation on the point code
of Q, its torsion translates, and their heights. By Lemma 8 and
Lemma 7 the whole system is single-fold in its auxiliaries once Q
is fixed.
Lemma 13 (existence and uniqueness of representatives). For each
integer j >= 1 there is exactly one representative in
(jP + T) ∪ (-jP + T). These are all the representatives.
Proof. Step 1: (P3) isolates the nontorsion coset representatives.
By (C2) and the height formula, W(t) = 1 for every t in T, so W(Q)=1
is exactly the set of torsion points. Conversely, for Q = jP + t
with j >= 1, W(Q) = W_j >= W_1 > 1. So (P3) excludes exactly the
torsion translates.
Step 2: in the coset jP + T, the x-coordinates are all distinct.
Suppose jP + t_1 and jP + t_2 have x-coordinate equal. Then they
are equal or negatives. Equality of x is equality or negation; if
they are equal, t_1 = t_2; if they are negatives, (jP + t_1)
+ (jP + t_2) = O, i.e. 2jP is a torsion point. But 2jP has hhat
= 4 j^2 hhat(P) > 0, so it is not torsion, contradiction. Hence the
x-coordinates are distinct.
Therefore the finite set (jP + T) has a unique point of maximal
x-coordinate. Call it Q_j^+. By (P1) it is not O (jP + t ≠ O since
j >= 1 and hhat(jP+t) = j^2 hhat(P) > 0); and (P5) admits exactly
that point. In the same way the coset (-jP + T) has a unique point of
maximal x-coordinate. Let us call it Q_j^-; it equals -Q_j^+ by the
definition of negation on E. Both have the same x-coordinate:
x(Q_j^-) = x(Q_j^+).
Step 3: exactly one of Q_j^+, Q_j^- has y-coordinate >= 0. Indeed,
y(Q_j^-) = -y(Q_j^+), because their x-coordinates are equal and
points of E with equal x are equal or negatives. Also neither y is
zero: an affine rational point of E with y = 0 is one of (0,0),
(5,0), (-5,0), which are torsion, and no point of jP+T or -jP+T
(j >= 1) is torsion. So y(Q_j^+) and -y(Q_j^+) are two nonzero
reals of opposite sign, and exactly one is >= 0; (P2) selects it.
Step 4: that unique selected point satisfies all of (P1)-(P5).
(P1) and (P2) hold by construction. (P3) holds because W > 1 on
jP + t (j >= 1, t in T). (P4): jP + t + s = O with j >= 1, t, s
in T, is impossible. (P5): Q_j^+ is by construction the maximum-x
point of its coset. So the selected point is a representative.
Step 5: any representative is one of these. Any Q in (jP+T) ∪
(-jP+T) with W(Q) > 1 lies in one of the two cosets. Its x must be
the maximum in that coset (because (P5) forces x(Q) >= x(Q + t) for
all t and the coset has distinct x-coordinates). Its y must be
>= 0 (by (P2)), which is exactly (P2) applied to Q_j^+ or Q_j^-. So
Q equals the selected representative. []
Notation. Write Q_j for the representative of absolute index j
(j >= 1). We have Q_j in (jP + T) ∪ (-jP + T), and W(Q_j) = W_j.
Single-fold system for "Q is a representative". Because the
conditions (P1)-(P5) are a finite conjunction of polynomial
relations on the point code of Q, on the four codes Q+t (t in T),
on the four heights W(Q+t), and on finitely many intermediate
points, Lemma 4(a) and Lemma 8 together give a single-fold
polynomial system in Q that recognises representatives.
5d. The function g.
Recall that W_1 = W(P) is a fixed positive integer. On input u in N,
define
(BR) u + W_1 is bracketed: find the unique k >= 1 with
W_k <= u + W_1 < W_{k+1}.
Existence and uniqueness of k: because (W_j) is strictly increasing
and unbounded, and u + W_1 >= W_1, there is exactly one such k. For
u = 0 the bracketing gives k = 1 (because W_0 = 1 <= W_1 = u + W_1
< W_2).
Now we need a second representative R, of index r = k^2. We express
r = k^2 by a "square window" that uses only products, comparisons,
and heights. The trick is the identity
(2k)^2 - 2 k^2 - ( (r+1)^2 - r^2 ) + 1 = 2 (k^2 - r).
This is the difference of two quadratics, and it is exactly the
linear combination of j^2's that makes the quadratic terms cancel
leaving only k^2 - r. Plug in the height formula a_E j^2 + eps_j:
log [ W([2]Q) * W(R) * W_1 ]
- log [ W(Q)^2 * W(R+P)max(W(R+P), W(R-P)) ]
Let us write this in terms of indices. The point [2]Q has absolute
index 2k; the point Q has absolute index k; the point Q+P has index
k+1; Q-P has index k-1. The point R has index r; R+P, R-P have
indices r+1 and r-1, whichever applies. The relevant products are
L_0 := W([2]Q) * W(R) * W_1,
D_0 := W(Q)^2 * max{ W(R+P), W(R-P) }.
For positive indices (which is always the case here since k >= 1,
r >= 1), substituting W_j = exp(a_E j^2 + eps_j):
log L_0 - log D_0
= a_E ( (2k)^2 + r^2 + 1 ) - a_E ( 2 k^2 + (r+1)^2 )
+ (e)
= a_E (2 k^2 - 2 r) + e = 2 a_E (k^2 - r) + e,
where max(W(R+P), W(R-P)) is W_{r+1} by the same "coset has distinct
x, so max is on the +side" argument that we used to bracket Q. The
error term e has |e| <= 6 c_E: one term each from W([2]Q), W(R),
W_1, and W_{r+1}, and two terms from W(Q)^2.
Now impose the multiplicative window
(WIN) L_0 <= kappa * D_0 and D_0 <= kappa * L_0,
which is equivalent to
1 / kappa <= L_0 / D_0 <= kappa.
Taking logs, | log (L_0/D_0) | <= log kappa. Now:
- If r = k^2, then log(L_0 / D_0) = e, and |e| <= 6 c_E < log kappa
by the choice of kappa. So (WIN) is satisfied.
- If r != k^2, then |k^2 - r| >= 1, so
| log(L_0 / D_0) | >= 2 a_E - 6 c_E > log kappa
by the choice of a_E. So (WIN) fails.
Therefore (WIN) is exactly equivalent to r = k^2, subject to the
uniqueness of Q and R in their cosets.
Putting it together, define
g(u) = W(R), where R is the representative of index r = k^2,
uniquely determined by (WIN).
Proposition 14 (the growth function). The graph of g : N -> N is
single-fold. There are real delta > 0 and integer u_0 >= 4 such
that for all u >= u_0,
delta (log u)^2 < log g(u) < u * log u.
Proof. Step 1 (single-foldness). On input u, a complete witness
tuple for "g(u) = c" consists of the following data, all unique:
- the point Q with representative, and its unique representative
tuple, satisfying (BR);
- the point R with representative, and its unique representative
tuple, satisfying (WIN);
- the fixed scalar-chains for [2]Q, Q+P, Q-P, R+P, R-P;
- the products L_0 and D_0;
- the output c = W(R), along with the final "c = W(R)" defining
equality.
Each of these is single-fold once its inputs are fixed: representative
by Lemma 13, addition of a fixed point and scalar multiplication by
Lemma 8, W by Lemma 7 (maximum of numerator absolute value and
denominator), and the window by Lemma 4(c). (BR) forces exactly one
k; (WIN) forces exactly one r = k^2. So for every u there is at
least one witness tuple, and it is unique. This proves totality
and single-foldness.
Step 2 (growth). Write U = u + W_1. The bracket (BR) says
W_k <= U < W_{k+1}. Taking logs:
a_E k^2 - c_E <= log W_k <= log U < log W_{k+1}
<= a_E (k+1)^2 + c_E.
So a_E k^2 <= log U + c_E and a_E (k+1)^2 >= log U - c_E.
Since k >= 1, we have (k+1)^2 <= 4 k^2, hence from the second
bound log U - c_E <= 4 a_E k^2, i.e.
k^2 >= ( log u - c_E ) / (4 a_E).
For large u this is >= log u / (8 a_E). So
log g(u) = log W_{k^2} >= a_E k^4 - c_E >= a_E (log u)^2 / (64 a_E^2) - c_E
= (log u)^2 / (64 a_E) - c_E.
For u large enough this is > (log u)^2 / (128 a_E). Take
delta = 1/(128 a_E).
For the upper bound: from the first estimate, log U >= a_E k^2 - c_E,
so a_E k^2 <= log U + c_E <= log U + c_E. Then log W_{k^2} =
a_E k^4 + eps_{k^2} <= a_E ((log U + c_E)/a_E)^2 + c_E =
(log U + c_E)^2 / a_E + c_E. This is O((log u)^2). In particular
(log U + c_E)^2 / a_E + c_E < u log u for all sufficiently large u,
so choose u_0 >= 4 larger than that threshold. []
The real constants (kappa, a_E, c_E, delta) are not coordinates of
the polynomial system. They only justify the choice of fixed
integers m_*, and they only appear in the proofs of the growth
bounds. The only quantities that enter the system itself are the
fixed integer m_*, the fixed integer kappa, and the fixed points
P and T; all of these are inserted by their integer codes.
------------------------------------------------------------------------
6. PELL SEQUENCES.
------------------------------------------------------------------------
For integers a >= 2, put D = a^2 - 1 (so D >= 3 and D is not a square).
For each i >= 0 there are unique integers x_i(a), y_i(a) with
(a + sqrt D)^i = x_i(a) + y_i(a) sqrt D.
Explicitly, x_0 = 1, y_0 = 0, x_1 = a, y_1 = 1, and both sequences
obey the same recurrence x_{i+2} = 2a * x_{i+1} - x_i and
y_{i+2} = 2a * y_{i+1} - y_i.
Lemma 15 (Pell sequences). Let a >= 2 and D = a^2 - 1.
(P1) Every positive integer solution (x, y) of x^2 - D y^2 = 1
is (x_i(a), y_i(a)) for exactly one i >= 1.
(P2) y_i(a) = i (mod a-1) for every i >= 0.
(P3) For every i >= 1,
(2a - 1)^{i-1} <= y_i(a) <= (2a)^{i-1}.
(P4) For integers b >= 2, u >= 2, n >= 0,
b^n <= y_{n+1}(b u) / y_{n+1}(u)
<= b^n (1 + 1/(2u-1))^n.
Proof.
(P1). Write alpha = a + sqrt D. Then alpha * (a - sqrt D) = 1, so
both alpha and its inverse 1/alpha = a - sqrt D lie in Z[sqrt D]. Any
positive solution (x, y) has beta := x + y sqrt D > 1 and norm one;
choose the unique integer i >= 0 with
1 <= gamma := beta * alpha^{-i} < alpha.
Since alpha and beta are both units of Z[sqrt D] of norm 1, gamma is
also a unit of Z[sqrt D], say gamma = x' + y' sqrt D with x', y' in Z.
Its norm is one, so x' = (gamma + 1/gamma)/2 and y' = (gamma - 1/gamma)/(2 sqrt D).
If gamma > 1, then x' > 0 and y' > 0, so y' >= 1, hence
x'^2 = 1 + D y'^2 >= 1 + D >= a^2, so x' >= a and gamma >= a + sqrt D >= alpha,
contradicting gamma < alpha. So gamma = 1, beta = alpha^i. Since
beta > 1, i >= 1. Uniqueness of i follows from alpha > 1.
(P2). Reduction modulo (a-1): a ≡ 1 (mod a-1), so the recurrence
y_{i+2} = 2a y_{i+1} - y_i becomes y_{i+2} ≡ 2 y_{i+1} - y_i
(mod a-1). Starting from y_0 = 0, y_1 = 1, induction gives y_i ≡ i
(mod a-1).
(P3). Define R_i := y_{i+1}(a) / y_i(a) for i >= 1. The recurrence
gives R_1 = 2a and R_{i+1} = 2a - 1/R_i. Inductively, if
2a - 1 <= R_i <= 2a then 2a - 1/R_i satisfies the same bounds:
since R_i >= 1, 1/R_i <= 1, so 2a - 1/R_i >= 2a - 1; and 1/R_i >= 0
gives 2a - 1/R_i <= 2a. So 2a - 1 <= R_i <= 2a for all i >= 1. Since
y_{i+1} = y_1 * R_1 * ... * R_i = R_1 * ... * R_i, this yields
y_{i+1} >= (2a-1)^i and y_{i+1} <= (2a)^i, i.e. (P3) after indexing
by i.
(P4). We have R_i(bu) >= b * R_i(u) for every i >= 1: for i = 1
both sides equal 2bu; and the induction step is
R_{i+1}(bu) - b R_{i+1}(u)
= 2bu - 1/R_i(bu) - b(2u - 1/R_i(u))
= -1/R_i(bu) + b/R_i(u)
= (b R_i(bu) - R_i(u)) / (R_i(bu) R_i(u))
>= (b * b R_i(u) - R_i(u)) / (R_i(bu) R_i(u)) (induction)
= R_i(u) (b^2 - 1) / (R_i(bu) R_i(u))
> 0.
So the product of ratios y_{n+1}(bu)/y_{n+1}(u) = prod_{i=1}^n
R_i(bu)/R_i(u) is >= b^n.
Upper bound: (P3) gives R_i(bu) <= 2bu and R_i(u) >= 2u-1, so
R_i(bu)/R_i(u) <= 2bu/(2u-1) <= b(1 + 1/(2u-1)). Product over
i = 1, ..., n gives <= b^n (1 + 1/(2u-1))^n.
For n = 0 both products are empty and y_1(bu)/y_1(u) = 1 = b^0, so
the statement holds. []
A numerical fact that will be used. For u >= 4,
u^u < (2u - 1)^{u-1}.
Proof. Define f(u) := (2 - 1/u)^{u-1} / u. Then f(4) = (7/4)^3 / 4 =
343/256 > 1. To see that f is strictly increasing on integers u >= 4,
write 2 - 1/u = (2u-1)/u and 2 - 1/(u+1) = (2u+1)/(u+1), and
compute
f(u+1)/f(u) = (u/(u+1)) * (2 - 1/(u+1))^u / (2 - 1/u)^{u-1}
= (2u-1)/(u+1) * R^u,
R := (2u+1)u / ((u+1)(2u-1)).
The numerator of R exceeds the denominator by exactly one:
(2u+1)u - (u+1)(2u-1) = 2 u^2 + u - (2 u^2 + u - 1) = 1.
Hence R > 1 and R^u > 1, so f(u+1)/f(u) > (2u-1)/(u+1) > 1 for u >= 3.
Thus f is strictly increasing on u >= 4, and f(4) > 1 gives f(u) > 1
for every u >= 4. But f(u) > 1 says (2u-1)^{u-1} > u^u. []
------------------------------------------------------------------------
7. THE POWER GRAPH POW(b, n, c).
------------------------------------------------------------------------
Throughout this section we assume g : N -> N satisfies the
single-fold graph and growth hypothesis of Proposition 14. Recall:
(GH) delta (log u)^2 < log g(u) < u log u for u >= u_0,
with u_0 >= 4.
Fix the constant
(ELL) l > 3 / (delta * log 2).
The constant l is a positive integer fixed once and for all by (GH).
Theorem 16 (Pow). Let g satisfy the hypothesis (GH). Then the
relation
Pow(b, n, c) <=> b >= 2 and c = b^n
on (b, n, c) in N^3 has a complete single-fold Diophantine
representation. That is, for every (b, n, c), the value c together
with every other auxiliary coordinate is unique when the relation
holds, and no solution exists otherwise.
Proof.
Step 1 (the system). All variables below range over N.
u = (c + 1)^l * (n + 1) * (b + 1) + u_0 ,
v = g(u) ,
X^2 - ( (bu)^2 - 1 ) F^2 = 1 ,
Y^2 - ( u^2 - 1 ) H^2 = 1 ,
0 < F < v , 0 < H < v ,
F = n + 1 + (bu - 1) q , H = n + 1 + (u - 1) q' ,
F = c H + r with r < H ,
b >= 2 .
Each inequality is a slack (Section 2). "v = g(u)" is one call to the
single-fold graph of g. The product (c+1)^l is polynomial (unfold as
a fixed number of multiplications). The whole system is a finite
conjunction of single-fold systems; the coordinates (b, n, c) are the
"inputs" of the outer system and are chosen freely.
Step 2 (soundness: c is forced). Take any solution. First note that
b >= 2 and u >= (c + 1)^l + u_0 >= u_0 >= 4. Let i >= 1 be the Pell
index of (X, F) in the first Pell equation: by Lemma 15, F = y_i(bu).
Similarly let j >= 1 be the Pell index of (Y, H): H = y_j(u).
Numerical bound on the indices. By (GH), v = g(u) < u^u. By
Lemma 15 (P3), y_i(bu) >= (2bu - 1)^{i-1} >= (2u-1)^{i-1}. And
F < v < u^u < (2u - 1)^{u-1}. So (2u-1)^{i-1} < (2u-1)^{u-1}, i.e.
i - 1 < u - 1, i.e. i < u. Similarly 1 <= j < u.
So 1 <= i, j < u. Also n + 1 < u: indeed (n + 1)(b + 1) <= u - u_0
<= u - 1 and b >= 2, so n + 1 <= (u-1)/3 < u - 1 < u.
Pinning i and j. By Lemma 15 (P2), y_i(bu) ≡ i (mod bu - 1).
Also F = y_i(bu) = n + 1 + (bu - 1) q by the third and fifth
equations, so F = y_i(bu) ≡ n + 1 (mod bu - 1). Hence
i ≡ n + 1 (mod bu - 1). Both i and n + 1 lie in [1, u - 1], and
u - 1 < bu - 1 since b >= 1. So i = n + 1.
Similarly, j = n + 1 (using the fourth Pell equation and the
sixth relation).
So F = y_{n+1}(bu) and H = y_{n+1}(u). By (P4),
b^n <= F / H <= b^n (1 + z)^n , z = 1/(2u - 1).
Error estimate. We want 0 <= F/H - b^n < 1. From the estimates just
given,
F/H - b^n <= b^n * ((1 + z)^n - 1) <= b^n * n z / (1 - n z),
where we used the binomial theorem (if n z < 1: 1 + z <= e^z gives
(1+z)^n - 1 <= (1 - nz)^{-1} * nz, or compute the geometric sum).
Here n z = n / (2u - 1) < 1 because u >= (n+1)(b+1) + u_0 >= 3(n+1) + 4
> (n+1)/2.
Also, F = c H + r with 0 <= r < H, so c = floor(F/H). Since
b^n <= F/H < b^n + 1 (because b^n * nz/(1 - nz) < 1), the integer
floor of F/H is b^n. Hence c = b^n.
We check the bound b^n * nz / (1 - nz) < 1. Here nz = n/(2u-1) < 1
by the earlier observation n < u. Then
1 - nz = (2u - 1 - n)/(2u - 1),
so
b^n * nz / (1 - nz) = b^n * n / (2u - 1 - n).
The bound u >= (c + 1)(n + 1)(b + 1) + u_0 with c = b^n and b >= 2
gives u >= 3(c + 1)(n + 1) + 4, hence
2u - 1 - n >= 6(c + 1)(n + 1) + 7 - n > 2 b^n n = 2 c n.
So b^n * n / (2u - 1 - n) < 1/2 < 1.
Step 3 (existence). Fix any (b, n) with b >= 2 and n >= 0, and let
c := b^n. Define u by the first equation. Take v = g(u); this exists
and is unique by the hypothesis. Define
F := y_{n+1}(b u) , X := x_{n+1}(b u) ,
H := y_{n+1}(u) , Y := x_{n+1}(u) ,
q := (F - n - 1) / (b u - 1) ,
q' := (H - n - 1) / (u - 1) ,
r := F - c H.
All these are natural numbers:
- F >= (2bu - 1)^n >= n + 1 by (P3), and F ≡ n + 1 (mod bu - 1)
by (P2), so q is a nonnegative integer;
- H >= (2u - 1)^n >= n + 1, and H ≡ n + 1 (mod u - 1), so q' is
a nonnegative integer;
- F/H >= b^n = c by (P4); since (P4) also gives F/H - b^n < 1 by
Step 2 (same error estimate, with the same u), r = F - cH
satisfies 0 <= r < H.
The Pell equations hold by construction.
The cutoff 0 < F < v. We have F > 0. And
log F <= log( (2bu)^n ) = n log(2bu)
<= n * 3 log u (because b < u and 2 < u)
<= (3/(l log 2)) * (log u)^2 (because u >= (c+1)^l,
c = b^n = e^{n log b},
so log u >= l n log b >= l n log 2,
hence n <= log u / (l log 2))
< delta (log u)^2 (because l > 3/(delta log 2))
< log v (by the growth hypothesis).
The last inequality uses u >= u_0. So 0 < F < v. Similarly 0 < H < v.
So a full witness exists.
Step 4 (uniqueness). For fixed (b, n, c), the argument of Step 2
fixes c = b^n first (so no c other than b^n is possible), then u by
the first equation, then v by the graph of g. With i = j = n + 1
pinned by (P2) and the bound i, j < u, F = y_{n+1}(bu) and
H = y_{n+1}(u) are fixed; so are X and Y (nonnegative square roots
of 1 + (D F^2) are unique). q, q', r are then forced by the residue
and division equations. Every slack is determined by its defining
inequality. Thus the entire witness tuple is unique.
The case c is not b^n is impossible by Step 2. So Pow is single-fold.
Together with the single-fold graph of g from Proposition 14, the
proposition is proved. []
------------------------------------------------------------------------
8. BINARY CONTAINMENT x << y.
------------------------------------------------------------------------
Recall that x << y means: every binary digit of x that is 1 is also
1 in the binary expansion of y. The key observation is a classical
parity criterion for binomial coefficients.
Lemma 17 (Lucas, base 2). For nonnegative integers x and y, the
binomial coefficient binom(y, x) is odd if and only if x << y.
Proof. Work in the polynomial ring F_2[Z]. Repeated squaring in
characteristic two gives (1+Z)^{2^i} = 1 + Z^{2^i} for every i.
Hence
(1+Z)^y = product_{i : y_i = 1} (1 + Z^{2^i}),
where y = sum_i y_i 2^i is the binary expansion of y, y_i in {0,1}.
When we expand the product, each monomial is obtained by choosing,
independently for each i with y_i = 1, whether to include the factor
Z^{2^i}. The resulting exponent is
sum_{i in S} 2^i
for some subset S of the 1-bit positions of y. Binary expansion is
unique, so distinct subsets S produce distinct exponents. Therefore
the coefficient of Z^x in F_2[Z] is 1 iff x = sum_{i in S} 2^i for
some such S, i.e. iff x << y. That coefficient is binom(y,x) mod 2.
So binom(y,x) is odd iff x << y. []
Lemma 18 (binary containment is single-fold). The relation x << y
on N^2 has a complete single-fold Diophantine representation.
Proof. Consider the following system of polynomial equations and
inequalities in the variables x, y, B, H, N, s, d, r, t (all in N):
(SUB1) x <= y.
(SUB2) B = 2^{y+1} (one Pow call: Pow(2, y+1, B)).
(SUB3) H = B^x (one Pow call: Pow(B, x, H)).
(SUB4) N = (B+1)^y (one Pow call: Pow(B+1, y, N)).
(SUB5) N = s B H + d H + r,
d < B (a slack: d + 1 + d' = B for some d' in N),
r < H (a slack: r + 1 + r' = H for some r' in N),
d = 2 t + 1 (oddness).
The three Pow calls each have single-fold Diophantine systems by
Theorem 16, since their bases 2, B, B+1 are each >= 2. B >= 4
because y+1 >= 1, and B+1 >= 2 trivially (B >= 2 since 2^{y+1} >=
2^1).
Soundness. Suppose the system holds. By (SUB2)-(SUB4),
B = 2^{y+1} and H = B^x. The binomial theorem gives
N = (B+1)^y = sum_{j=0}^{y} binom(y, j) B^j.
Each binomial coefficient satisfies binom(y, j) <= sum_j binom(y, j)
= 2^y < B = 2^{y+1}, so the display is exactly the base-B expansion
of N with all digits < B (no carries).
Equation (SUB5) says N = (s B + d) H + r with r < H. So
floor(N / H) = s B + d, N mod H = r,
and then floor((s B + d) / B) = s, (s B + d) mod B = d with d < B.
Now H = B^x, so
floor(N / H) = floor(sum_{j=0}^{y} binom(y,j) B^{j - x})
= sum_{j=x}^{y} binom(y,j) B^{j-x} (since B has
integer powers; term-by-term division is exact
because all exponents j-x >= 0)
with remainder r = sum_{j=0}^{x-1} binom(y,j) B^j < H. Then
floor(floor(N/H) / B) = sum_{j=x+1}^{y} binom(y,j) B^{j-x-1},
and the low digit of floor(N/H) in base B is exactly binom(y,x).
So d = binom(y,x). (The case x = y gives floor(N/H) = binom(y,y) = 1
and d = 1; the case x = 0 gives d = binom(y,0) = 1.)
By Lemma 17, d odd iff binom(y,x) odd iff x << y. The final equation
d = 2t+1 forces d odd. So the system implies x << y.
Completeness. If x << y, take B := 2^{y+1}, H := B^x,
N := (B+1)^y, d := binom(y,x) (odd by Lemma 17), r := N mod H,
s := (floor(N/H) - d)/B, t := (d-1)/2. All constraints hold; every
value is a natural number; and the three Pow calls have their unique
witnesses by Theorem 16.
Uniqueness. Fix (x, y) satisfying x << y. The Pow calls fix B, H, N
(and all their internal auxiliary coordinates) by Theorem 16.
The division (SUB5) fixes (s, d, r) uniquely (standard quotient-
remainder uniqueness). The oddness equation fixes t = (d-1)/2.
Every slack is determined by its defining inequality. So the whole
tuple is unique.
Edge case x = y = 0. Then B = 2, H = 1, N = 1, s = r = t = 0, d = 1.
All constraints are satisfied with these unique values. []
------------------------------------------------------------------------
9. REWRITING A HALTING RUN OF A COUNTER MACHINE.
------------------------------------------------------------------------
This section converts a counter machine (the universal model from
Lemma 19 below) into a single-fold Diophantine system whose
solutions are exactly the halting runs on a given input. Subsection
9a fixes the machine model and the constants. Subsection 9b writes
down the polynomial system using Pow and <<. Subsection 9c proves
that the system is exactly what we want.
9a. The counter machine.
Definition. A counter machine M has:
- a finite set Q of states, with distinguished q_* (start) and
h (halt) in Q,
- r counters indexed 1, ..., r, each holding a value in N,
- for each nonhalt state q, exactly one instruction, either
INC(j, q'): counter j += 1, then go to state q';
TESTDEC(j, q', q''): if counter j = 0, go to q';
otherwise, counter j -= 1, then go to q''.
The halt state h has no instruction; a configuration with state h
is terminal.
A configuration at input (a_1, ..., a_r) starts at (q_*, a_1, ...,
a_r) and proceeds deterministically. Because the machine is
deterministic and total except at the halt state, for each input
there is at most one halting run.
Lemma 19 (counter machines are universal). For every n >= 1 and
every recursively enumerable S <= N^n there is a counter machine M
with n distinguished input counters such that M with input
(a_1, ..., a_n) in those counters and 0 elsewhere halts iff
(a_1, ..., a_n) in S.
Proof. Standard. A Turing machine with tape can be simulated with
two stacks (left and right of the head), each held as one integer
using a fixed base D >= 2 with one digit per symbol. Push and pop
on a stack are finitely many INC / TESTDEC instructions (a push
multiplies the stack by D and adds the new digit; a pop divides
by D and reads the remainder). The finite control of the Turing
machine is the state set of the counter machine. See Minsky 1961
and Shepherdson-Sturgis 1963 for details. []
Fix M as in Lemma 19. Let
s = |Q| number of states,
r number of counters,
d_1, ..., d_r input values (each d_j is 0 or an a_i),
and define
C := 1 + s + sum_{j=1}^r d_j.
We have s >= 1 so C >= 2. Along any run of length t, each counter
value is at most d_j + t (each INC instruction adds 1, each other
instruction subtracts at most 1), so < C + t. In particular, at the
halting time T, each counter is bounded by C + T; the "clock"
C + t below will keep them below B/2.
Arcs. For each state q in Q \ {h}, its unique instruction gives one
or two "arcs" into successor states:
INC(j, q') from q: one arc, from q to q', labeled +j.
TESTDEC(j, q', q'') from q: two arcs, from q.
- arc labeled 0j, to state q';
- arc labeled -j, to state q''.
Let A be the set of arcs. Define
A_j^+ = arcs labeled +j,
A_j^- = arcs labeled -j,
j(a) = the counter affected by arc a,
source(a) = the state from which a emanates,
dest(a) = the state to which a points.
Then |A| <= 2 s, since each nonhalt state gives at most two arcs.
9b. The encoding system.
All variables below range over N. The display coordinates are:
w, B, b, k, H, J, M (7 naturals)
I_q for each q in Q (s naturals)
Z_q, N_q, V_q for each test state q (3 tau naturals)
R_j, rho_j, eta_j for each j = 1, ..., r (3r naturals)
R_0, rho_0, eta_0 (3 naturals)
where tau = number of test states. Auxiliary coordinates from Pow
calls, << calls, and slacks are additional but also finite; see
Appendix A for the exact count.
Base and time:
(M1) Pow(2, w, B) [B = 2^w]
(M2) B = 4 b
(M3) B > 2 C [slack]
(M4) k > 0 [slack]
(M5) Pow(B, k, H) [H = B^k]
(M6) B J = H
(M7) (B - 1) M = H - 1 [M = sum_{t=0}^{k-1} B^t]
State masks:
(M8) I_q << M for every q in Q
(M9) sum_{q in Q} I_q = M
Test-branch masks, for every nonhalt state q with TESTDEC:
(M10) Z_q << I_q, N_q << I_q
(M11) Z_q + N_q = I_q
(M12) Z_q + V_q = M
State transition: for each q in Q,
(M13) I_q = delta_{q, q_*} + B * sum_{a in A, dest(a) = q} E_a
where delta_{q, q_*} = 1 if q = q_*, else 0, and E_a is defined by:
if a is an INC-arc from q_0: E_a = I_{q_0};
if a is the 0j arc of a TESTDEC from q_0: E_a = Z_{q_0};
if a is the -j arc of a TESTDEC from q_0: E_a = N_{q_0}.
Counter masks, for every j = 1, ..., r:
(M14) R_j << (2b - 1) M [permitted block digits]
(M15) R_j = rho_j J + eta_j, eta_j < J
(M16) R_j = d_j + B * ( R_j - rho_j J
+ sum_{a in A_j^+} E_a
- sum_{a in A_j^-} E_a )
Zero-test mask, for each nonhalt state q with TESTDEC on counter j(q):
(M17) R_{j(q)} << (B - 1) V_q
Clock:
(M18) R_0 << (2b - 1) M
(M19) R_0 = rho_0 J + eta_0, eta_0 < J
(M20) R_0 = C + B * ( R_0 - rho_0 J + M - J )
(M21) b <= rho_0 [weak inequality: slack]
(M22) 2 rho_0 < B [strict inequality: slack]
All displayed equations are polynomial equations, all displayed
inequalities are single slacks (Section 2). The whole system is a
finite conjunction of single-fold systems (each Pow call by Theorem
16, each << call by Theorem 18) with plain polynomial identities
and slacks. So it is single-fold once its inputs (the input tuple
(d_1, ..., d_r)) are fixed.
Interpretation. The block structure (base-B digits, each block of
w binary digits, so each block in [0, B-1]) is meant to index time
0, 1, ..., k-1. The digit of I_q at block t is 1 iff the run is in
state q at time t. The digit of Z_q (resp. N_q) at block t is 1 iff
at time t the run is in test state q and chooses the zero (resp.
decrement) branch. R_j at block t is v_j(t), the value of counter j
at time t. R_0 at block t is C + t (the clock). The final block
k-1 is the halt time, forced by the clock equations (M21)-(M22) and
by the dyadic interval choice of B that we make in the witness.
The rest of Section 9c proves this interpretation is correct.
9c. The main lemma about the encoding.
The rest of this section proves that the system of 9b is exactly
the encoding of a halting run: any solution corresponds to a halt,
and every halting run provides at least one solution, and it is
unique once the input is fixed. Lemmas 20-23 handle the "state
layer"; Lemma 24 handles "counters"; Lemma 25 handles "zero tests";
Theorem 26 assembles the compiler.
Lemma 20 (base digits decompose M, J, H). Under (M1)-(M7):
B = 2^w, H = B^k, J = B^{k-1}, M = sum_{t=0}^{k-1} B^t.
Proof. (M1) gives B = 2^w. (M5) gives H = B^k. (M6) gives
J = H/B = B^{k-1}. (M7) gives
M = (H - 1)/(B - 1) = (B^k - 1)/(B - 1) = sum_{t=0}^{k-1} B^t.
(The last equality requires B > 1, which holds because B > 2C >= 4.)
Lemma 21 (state partition). Under (M8)-(M9): for every block t in
[0, k-1], exactly one state mask I_q has block-t digit equal to 1,
and all other state masks have block-t digit 0. Moreover, no
state mask has any nonzero block outside [0, k-1].
Proof. By (M8), I_q << M. Since M has blocks 0..k-1 all equal to 1
(Lemma 20) and no others, every I_q has block digits in {0, 1} in
blocks 0..k-1 and 0 elsewhere. Summing over q, the block-t digit of
sum_q I_q is the number of q with I_q block-t = 1. By (M9) sum_q I_q = M,
whose block-t digit is 1. So exactly one q has I_q block-t = 1.
Lemma 22 (state transition, no carry, and halt at last block).
Under (M8)-(M13):
(a) For each state q, equation (M13) has no carries and precisely
describes the state transition;
(b) If q(t) denotes the unique state at time t, then q(t+1) is
the destination of the unique arc out of q(t), for every
t < k-1;
(c) q(t) ≠ h for every t < k-1, and q(k-1) = h.
Proof.
(a) For each q, the right of (M13) is delta_{q,q_*} + B times a sum of
arc masks E_a. Each E_a << M by Lemma 21, so has block digits in {0,1}.
The number of arcs destined for any fixed q is at most |A| <= 2s < B.
(Because B > 2C >= 2(1+s) = 2 + 2s > 2s.) So the sum over a has block
digits < B, hence no carries. Multiplying by B shifts block t to
block t+1. So block 0 of (M13) gives delta_{q,q_*}, and block
t+1 (t <= k-2) gives the count of arcs into q with block-t present.
Comparing with I_q's blocks: block t of I_q for t >= 1 equals
block t-1 of (sum_{a: dest(a)=q} E_a). No carry.
(b) Immediate from (a): the (unique) arc out of q(t) contributes
to state q(t+1), which by Lemma 21 is the unique state at block t+1.
(c) At t < k-1: if q(t) = h, then the halt state has no outgoing arc,
so E_a at block t are all 0 (each E_a has block t = 0 since the
underlying I or Z or N state mask has block t = 0 for the non-halt
states that have outgoing arcs; and h is not the source of any arc).
So block t+1 of I_q is 0 for every q, contradicting Lemma 21 at
block t+1 (only possible if t+1 >= k, i.e. t >= k-1). So q(t) ≠ h
for t < k-1.
For q(k-1): if q(k-1) ≠ h, then q(k-1) has an outgoing arc,
which would put its destination at block k. But sum_q I_q has
blocks 0..k-1 only, no block k. Contradiction. So q(k-1) = h.
Lemma 23 (halt mask and arc-mask identity). Under (M8)-(M13):
(a) I_h = J = B^{k-1}, and I_q for q ≠ h is I_q = sum of blocks
in [0, k-2] where q(t) = q;
(b) sum_{a in A} E_a = M - I_h.
Proof.
(a) By Lemma 22(c), q(k-1) = h and q(t) ≠ h for t < k-1. So I_h has
block k-1 = 1 and blocks 0..k-2 = 0. Hence I_h = B^{k-1} = J.
(b) Sum (M13) over all q:
sum_q I_q = sum_q delta_{q, q_*} + B sum_{a in A} E_a,
M = 1 + B sum_{a in A} E_a.
So sum_{a in A} E_a = (M - 1)/B.
On the other hand, M = sum_{t=0}^{k-1} B^t, and I_h = B^{k-1}.
So M - I_h = sum_{t=0}^{k-2} B^t = (B^{k-1} - 1)/(B - 1) = (J - 1)/(B-1).
And (M - 1)/B = (sum_{t=0}^{k-1} B^t - 1)/B = sum_{t=1}^{k-1} B^{t-1}
= sum_{s=0}^{k-2} B^s. Equal. So sum_{a in A} E_a = M - I_h.
Lemma 24 (counter digits). Under (M14)-(M16), for each counter j,
if we write R_j = sum_{t=0}^{k-1} r_{j,t} B^t with 0 <= r_{j,t} <= 2b-1
< B/2, then:
(a) r_{j,0} = d_j, and
(b) r_{j,t+1} = r_{j,t} + a_{j,t} - f_{j,t} for t = 0, ..., k-2,
where a_{j,t} in {0,1} is the indicator that the chosen arc at
time t is a +j arc and f_{j,t} in {0,1} is the indicator that
it is a -j arc. a_{j,t} + f_{j,t} <= 1 always, and both are 0
at t = k-1.
Proof. (M14) says R_j << (2b-1) M. Now M has blocks 0..k-1 all 1, so
(2b-1) M has blocks 0..k-1 all 2b-1 and no others. So R_j has block
digits in [0, 2b-1] in blocks 0..k-1. (M15) says R_j = rho_j J + eta_j
with eta_j < J = B^{k-1}; so rho_j is the block k-1 digit and eta_j
the low part. (In particular rho_j = r_{j,k-1}.)
Now rearrange (M16). R_j - rho_j J = sum_{t=0}^{k-2} r_{j,t} B^t. And
sum_{a in A_j^+} E_a = sum_{t=0}^{k-2} a_{j,t} B^t + a_{j,k-1} B^{k-1}.
Since a_{j,k-1} = 0 (the chosen arc at t = k-1 does not exist, because
q(k-1) = h has no outgoing arc), this is sum_{t=0}^{k-2} a_{j,t} B^t.
Similarly for A_j^-.
So (M16) reads:
sum_{t=0}^{k-1} r_{j,t} B^t = d_j
+ B sum_{t=0}^{k-2} r_{j,t} B^t
+ B sum_{t=0}^{k-2} (a_{j,t} - f_{j,t}) B^t
= d_j + sum_{t=1}^{k-1} (r_{j,t-1} + a_{j,t-1} - f_{j,t-1}) B^t.
Coefficient-wise (coefficients in [-B/2+1, B/2-1] for the middle
terms, or |d_j| < B/2 in block 0), so all coefficients are in
(-B, B). The only way the B-adic expansion on both sides can match
with all coefficients |c_t| < B is c_t = 0 for every t. Thus:
r_{j,0} = d_j,
r_{j,t} = r_{j,t-1} + a_{j,t-1} - f_{j,t-1} for t = 1, ..., k-1.
After shifting the index, this is the claim.
Lemma 25 (zero tests). Under (M17), for every non-halt state q with
TESTDEC on counter j(q):
whenever q(t) = q is a zero-branch time (i.e. the chosen arc at
t is the 0j arc, so the 0j mask Z_q has block t = 1), the counter
value r_{j(q), t} = 0.
Proof. (M17) says R_{j(q)} << (B-1) V_q. Since V_q = M - Z_q by (M12),
and Z_q has block digits 0/1 (since Z_q << I_q has block digits 0/1),
V_q has block digits 1 - Z_q = 0 or 1 (per block). (B-1) has block
digit B-1 in block 0 and 0 elsewhere. So (B-1) V_q is the number whose
block-t digit is (B-1) * (V_q block t). Thus (B-1) V_q has block-t
digit:
- B-1 (all bits 1) if V_q block t = 1,
- 0 if V_q block t = 0.
Now R_{j(q)} << (B-1) V_q means that if (B-1) V_q has block digit 0
at block t, then R_{j(q)} has block digit 0 at block t. So whenever
V_q block t = 0 (i.e. Z_q block t = 1, zero branch selected), we
get r_{j(q), t} = 0. That is the claim. (The reverse direction is not
claimed.)
Completeness of the encoding (existence):
Take any halting run C_0, ..., C_T of the machine on input
(a_1, ..., a_r). Set k = T + 1. Choose B a power of 2 with
2(C + T) < B <= 4(C + T). For each such L = C + T, there is exactly
one power of 2 in (2L, 4L]: take the smallest power of 2 that exceeds
2L; it is <= 4L and unique. Set b = B/4 (integer since B is a power
of 2 and B >= 8 since C >= 2, B > 2C >= 4 means B >= 8). Set w =
log_2 B, H = B^k, J = B^{k-1}, M = sum_{t=0}^{k-1} B^t. These
satisfy (M1)-(M7) by Lemma 20.
Concretely:
- I_q has block-t digit 1 iff the run at time t is in state q.
- Z_q has block-t digit 1 iff time t has state q and the 0-branch
was chosen.
- N_q has block-t digit 1 iff time t has state q and the -branch
was chosen. So Z_q + N_q = I_q (each test state at time t picks
one branch).
- V_q = M - Z_q has block-t digit 0 at the zero branches and 1
elsewhere.
- R_j has block-t digit 0 <= v_j(t) (the counter value at time t).
Since v_j(t) <= d_j + t < C + t < C + T < B/2, and 2b - 1 =
B/2 - 1, we have v_j(t) <= B/2 - 1. So R_j << (2b - 1) M holds.
- rho_j = v_j(T), the final counter value.
- R_0 has block-t digit C + t. rho_0 = C + T. That is, rho_0 = C + k - 1.
- b <= rho_0 = C + T, because b = B/4 and B <= 4(C+T) by the
choice of B in (2(C+T), 4(C+T)].
- 2 rho_0 = 2(C+T) < B by choice of B.
Every equation (M1)-(M22) and every slack and every auxiliary
variable of every Pow and << call follows from these assignments by
construction, using Theorem 16 for the three Pow calls (Pow(2, w, B)
and Pow(B, k, H)) and Theorem 18 for each << call. So a witness
exists.
Soundness of the encoding. Take any solution. By Lemmas 20-25:
- The run is well-defined: exactly one state per time, states
propagate by destination-of-arc, halt occurs at time k-1 (Lemma 22).
- Every counter update (Lemma 24) is the correct counter update.
- Every zero test (Lemma 25) is the correct zero test.
- The clock R_0: apply the same coefficient argument as in Lemma 24
with d_j replaced by C and with the term M - J:
R_0 = C + B(R_0 - rho_0 J + M - J). Since R_0 - rho_0 J = sum_{t=0}^{k-2} r_{0,t} B^t
and M - J = sum_{t=0}^{k-2} B^t, we get:
sum_{t=0}^{k-1} r_{0,t} B^t = C + sum_{t=1}^{k-1} (r_{0,t-1} + 1) B^t.
Coefficient-wise: r_{0,0} = C and r_{0,t} = r_{0,t-1} + 1 for t >= 1.
So r_{0,t} = C + t and rho_0 = r_{0,k-1} = C + k - 1 = C + T
(since T = k - 1).
Combined with (M21), (M22): b <= C + T and 2(C + T) < B = 4b, so
B is in (2(C+T), 4(C+T)]. This interval contains exactly one
power of two, so B is forced; hence k = T + 1 is forced.
So every solution decodes to the actual run. And the run's state
sequence, branch sequence, and counter values are determined.
Uniqueness of the full tuple. Given a solution:
- The decoded run fixes T (the halting time), and thus k = T + 1.
- The clock bound forces B (unique power of two in the interval).
- Then w, b, H, J, M are forced (Lemma 20).
- The states I_q, test masks Z_q, N_q, V_q, and counters R_j are
forced by the run and by Lemmas 22-25.
- rho_j, eta_j are forced by division of R_j by J.
- rho_0, eta_0 are forced by division of R_0 by J.
- All slacks are determined.
- All Pow and << auxiliaries are determined (their single-fold
systems apply).
The only remaining concern is: for a fixed input (a_1, ..., a_r),
is there at most one halting run? Yes, because the machine is
deterministic. So the tuple is unique.
Conversely, for a nonhalting input, there is no halting run, so no
solution (by Soundness, any solution would give a halting run of
length T = k - 1 on the input).
This completes Section 9.
Theorem 26 (computation compiler). For every counter machine M and
initial counter values (d_1, ..., d_r), there is a finite single-fold
Diophantine system in the input tuple (d_1, ..., d_r), such that the
system has a solution iff the machine halts on (d_1, ..., d_r), and
when it does there is exactly one solution tuple, including all the
auxiliary coordinates.
Proof. Follows from the constructions and Lemmas 20-25 above. []
------------------------------------------------------------------------
10. PUTTING IT TOGETHER: THE POLYNOMIAL OF THEOREM 1.
------------------------------------------------------------------------
We have now assembled all the ingredients:
(A) a set S <= N^n, given; a counter machine M from Lemma 19 which
halts on exactly the members of S; write d_1, ..., d_r for its
initial counter values (each d_j is either 0 or one of the
input coordinates a_1, ..., a_n), and C = 1 + s + sum_j d_j;
(B) for each halting run on (d_1, ..., d_r), exactly one full
witness tuple (Theorem 26), consisting of:
- powers Pow(2, w, B) and Pow(B, k, H),
- for each state q, Pow-call for I_q << M,
- for each test-branch, Pow-call for Z_q << I_q or N_q << I_q,
- for each counter (including the clock), Pow-call for
R_j << (2b-1) M or R_j << (B-1) V_q,
- the plain equations (M1)-(M7), (M11), (M12), (M13),
(M15), (M16), (M19), (M20),
- all slacks (M3), (M4), (M14), (M17), (M18), (M21), (M22).
Each Pow and each << call is an instance of the corresponding
single-fold system from Theorem 16 or Theorem 18. Because these
systems introduce their own fresh auxiliary tuples and are single-
fold given their inputs, their use inside the machine-encoding
system is exactly the composition rule of Lemma 4(a)+(b).
Substitution. Let
w_1, ..., w_m
denote the complete tuple of auxiliary variables introduced by
expanding every Pow and << call into its polynomial system, and by
expanding every slack and every named expression; combined with the
displayed machine and state variables, they form the total witness
tuple w. Theorem 26 asserts that, for fixed input (a_1, ..., a_n),
the set of w so obtained is a singleton iff the machine halts.
Reduction to a single polynomial. The expanded system is a finite
list of polynomial equations
F_1(a, w) = 0, F_2(a, w) = 0, ..., F_N(a, w) = 0.
(Here a = (a_1, ..., a_n) is the input tuple; the counter-machine
inputs are among them or else 0.) Each F_i is an integer polynomial
in a and w.
Set
P(a, w) = F_1(a, w)^2 + F_2(a, w)^2 + ... + F_N(a, w)^2.
Since each F_i is an integer polynomial and squares are nonnegative,
P(a, w) = 0 iff F_i(a, w) = 0 for every i. This reduction adds no
variables and does not change the solution set. It is the standard
sum-of-squares trick.
Conclusion. For F_1 = ... = F_N = 0 to be the finite system from
Theorem 26, the identity
#{w in N^m : P(a, w) = 0} = 1 if a in S, 0 if a not in S
holds. This is the assertion of Theorem 1. []
------------------------------------------------------------------------
11. THE COROLLARY.
------------------------------------------------------------------------
Proof of Corollary 2. Fix any nonrecursive recursively enumerable
set S <= N. (Such a set exists; e.g. the halting set.) Apply
Theorem 1 with n = 1 to obtain m >= 1 and P in Z[A, W_1, ..., W_m]
representing S single-fold.
Set D = max{1, deg P}, an integer that depends only on P, not on a.
For each a in N, define
F_a(W_1, ..., W_m) := P(a, W_1, ..., W_m).
Each F_a is a polynomial in Z[W_1, ..., W_m] of total degree at most
D (= deg P), because substituting the constant a for A cannot raise
the total degree. By single-foldness of P:
#{w in N^m : F_a(w) = 0} = 1 if a in S, 0 if a not in S.
So the promise "# solutions <= 1" is satisfied by every F_a.
Computability. The map a |-> F_a is computable: given a, we compute
the coefficient list of F_a by substituting the constant a into the
(known, finite) coefficient list of P. This is a finite computation
from a and from the encoded coefficients of P.
Reduction to undecidability. Suppose, for contradiction, that an
algorithm A has the property stated in Corollary 2: on every input
polynomial F in Z[W_1, ..., W_m] of total degree at most D satisfying
"F has at most one zero in N^m", A halts and correctly decides
whether that zero exists.
Then the following algorithm decides membership in S: given a,
compute F_a (as a coefficient list) and run A on F_a. A's answer is
correct by assumption, and returns "S contains a" iff F_a has a zero,
which by single-foldness holds iff a in S. Since S is nonrecursive,
contradiction. []
Remarks.
(a) The bits in Corollary 2 are existential: the proof exhibits
no explicit m or D, only their existence. The polynomial P is
fixed, but its coefficient values are not displayed.
(b) The promise is "at most one" not "exactly one": no input
polynomial has more than one solution, but some have zero.
A decidable algorithm cannot exploit this promise unless it
can test zero-ness.
(c) The corollary does not address analogous uniqueness promises
for solutions in Z or Q. Those are different problems.
------------------------------------------------------------------------
APPENDIX A. THE COMPLETE WITNESS TUPLE, IN FULL.
------------------------------------------------------------------------
This appendix lists every coordinate that appears in the witness
tuple w of Theorem 1, and shows that each is uniquely determined by
the inputs and the previous coordinates. It is the "line-by-line"
form of the single-fold claim. If any step of the argument above
is unclear, the reader can use this appendix to verify that exactly
the claimed coordinates appear.
Primitive coordinates.
For a weak inequality F >= G, a slack variable s in N with
F - G = s. For a strict inequality F > G, s in N with
F - G = 1 + s. For a "naming" F = E, one variable in N equal
to E's value. Sign split z = z^+ - z^-, two variables with
z^+ z^- = 0.
Every slack and every named expression and every sign-split part
is uniquely determined by F, G, E, z, respectively.
Rational arithmetic.
Every rational code is (p, n, d, t, s, q) in N^6 satisfying
(R1)-(R3). By Lemma 6, exactly one code for each rational.
A rational addition or multiplication that produces a fresh output
code contributes the six coordinates of the output plus possibly
one slack for each comparison made inside the computation (e.g.
a "z_1 <= z_2" comparison contributes one slack after clearing
denominators).
Point arithmetic.
A point code is (o, code_x, code_y) with o in {0,1}. For o = 1,
both code_x and code_y are the canonical zero code (0,0,1,0,0,0).
For o = 0, code_x and code_y are valid rational codes satisfying
the curve equation. Unique for each rational point Q by Lemma 8.
A point addition Q_1 + Q_2 contributes:
- the output point code (three coordinates, one flag and two
rational codes, each of which is six naturals), total 13
naturals;
- seven selectors (Lemma 4(c)) in N per case;
- for the four "affine" cases 3, 4, 6, 7: a local slope code
(six naturals);
- four strict comparison slacks for the case guards x_1 < x_2,
x_1 > x_2, y_1 + y_2 = 0, y_1 = y_2 > 0, y_1 = y_2 < 0
(each comparison counted once).
The point addition of the fixed m_*Q chain repeats this whole
block once per addition in the chain. Fixed number of coordinates
per chain (bounded by m_* * 13 or so; the exact count is a fixed
constant).
Height calls.
Height of Q contributes: the scalar chain [m_*]Q (many point
additions, each of the above form) plus a fresh output integer
W(Q) and a maximum-of-two comparison (two selectors and one
local comparison slack per case).
Height comparisons of the form x(Q) >= x(Q+t) contribute one
strict comparison slack per t in T.
Representatives.
A "Q is a representative" block contributes:
- the point code for Q,
- the four point codes for Q+t (t in T), plus four point
additions and seven selectors each;
- the height outputs W(Q) and W(Q+t) across T (five heights);
- six comparison slacks per representative: one for y(Q) >= 0,
one for h(Q) > 1, four for x(Q) >= x(Q+t).
The growth function g(u).
A call g(u) = v contributes:
- the point code for Q (the unique representative satisfying
the bracket (BR));
- the four point codes Q+t for t in T (four additions);
- the point codes Q+P, Q-P (two additions, each using fixed
P as the second operand);
- the point Q' := [2]Q (one doubling);
- the four height outputs W(Q+t) (four height calls);
- the heights W(Q+P), W(Q-P) (two more);
- the "neighbor maximum" max{W(Q+P), W(Q-P)} (one
comparison block);
- four slacks in the bracket (BR): u+W_1 - h_Q, and
N_Q^Q - u - W_1 - 1 where N_Q^Q is the maximum neighbor of
W at Q;
- the second representative R with the same block as Q;
- the point codes R+P, R-P, [2]Q (five more additions);
- heights W(R+P), W(R-P), W(R) (three more heights);
- the "neighbor maximum" of R (one comparison block);
- the products L_0 = W([2]Q) * W(R) * W_1 and
D_0 = W(Q)^2 * (max neighbor of R);
- the four window slacks: kappa D_0 - L_0 and kappa L_0 - D_0;
- v = W(R), with the defining equation.
Since the representative block, the height block, and the addition
block each have a fixed number of coordinates, the whole g block
has a fixed number of coordinates, independent of u, k, and r.
Powers.
A call Pow(b, n, c) with output c contributes:
- the display variables u, v, X, Y, F, H, q, q', r (nine
naturals, some possibly zero);
- the call v = g(u) (the whole g block above);
- six slacks: b - 2, F - 1, v - F - 1, H - 1, v - H - 1,
H - r - 1;
- the square roots X, Y.
These are exactly the coordinates listed in the Pow system of
Theorem 16. The square roots are unique (nonnegative square roots
in N), so no sign split.
Binary containment.
A call x << y with x, y in N contributes:
- e := y + 1, A := B + 1 (where B is y+1's associated power);
- three full internal Pow tuples, one for Pow(2, e, B),
one for Pow(B, x, H), one for Pow(A, y, N);
- the display variables s, d, r, t;
- three slacks: y - x, B - d - 1, H - r - 1.
The three Pow calls contribute the whole Pow block each. The
display variables are unique by quotient-remainder and parity.
The machine encoding.
Let s (number of states), r (number of counters), tau (number of
test states) be fixed integers depending only on the machine M.
Display variables:
w, B, b, k, H, J, M (7 naturals)
(I_q) for q in Q (s naturals)
(Z_q, N_q, V_q) for each test state (3 tau naturals)
R_j, rho_j, eta_j for j in {1..r} (3r naturals)
R_0, rho_0, eta_0 (3 naturals)
total display: 7 + s + 3 tau + 3r + 3
= 10 + s + 3tau + 3r.
Auxiliary from slacks in (M3), (M4), (M14), (M17), (M18), (M21),
(M22):
(M3): B - 2C - 1;
(M4): k - 1;
(M14): (2b - 1) M - R_j - 1 for each j (r slacks);
(M17): (B-1) V_q - R_{j(q)} - 1 for each test state (tau slacks);
(M18): (2b - 1) M - R_0 - 1;
(M21): rho_0 - b;
(M22): B - 2 rho_0 - 1.
Auxiliary from Pow calls:
two internal Pow tuples, one for Pow(2, w, B) and one for
Pow(B, k, H).
Auxiliary from << calls:
s calls of I_q << M;
2 * tau calls of Z_q << I_q, N_q << I_q;
(r + 1) calls of R_j << (2b - 1) M for j = 0..r;
tau calls of R_{j(q)} << (B - 1) V_q.
Arc masks E_a are expressions in the display variables; they
introduce no new coordinates.
Faithfulness of the count. Every coordinate above is either (a) a
direct display value, (b) a unique slack, or (c) a coordinate of a
single-fold Pow or << call (whose internal coordinates are unique by
Theorem 16 or Theorem 18). Therefore, for fixed input (a_1, ..., a_n),
the whole auxiliary tuple is unique iff a solution exists, exactly
as Theorem 26 asserts.
The count is finite. s, tau, r, and the exact count of internal
coordinates inside Pow and << calls are all fixed integers, bounded
by a number that depends only on M and n. The witness tuple has
that many coordinates and no more; the base-B block size w and the
halting time T = k - 1 are part of the display, not additional
coordinates.
------------------------------------------------------------------------
REFERENCES.
------------------------------------------------------------------------
[1] M. Davis, H. Putnam, J. Robinson. The decision problem for
exponential Diophantine equations. Annals of Mathematics 74
(1961), no. 3, 425-436.
[2] Yu. V. Matiyasevich. The Diophantineness of enumerable sets.
Doklady Akademii Nauk SSSR 191 (1970), no. 2, 279-282.
[3] Yu. V. Matiyasevich. The existence of non-effectivizable estimates
in the theory of exponential Diophantine equations. Zapiski
Nauchnykh Seminarov LOMI 40 (1974), 77-93.
[4] Yu. V. Matiyasevich. Towards finite-fold Diophantine
representations. Zapiski Nauchnykh Seminarov POMI 377 (2010),
78-90.
[5] M. L. Minsky. Recursive unsolvability of Post's problem of "Tag"
and other topics in theory of Turing machines. Annals of
Mathematics 74 (1961), no. 3, 437-455.
[6] J. C. Shepherdson, H. E. Sturgis. Computability of recursive
functions. Journal of the ACM 10 (1963), no. 2, 217-255.
[7] J. P. Jones, Yu. V. Matiyasevich. Register machine proof of the
theorem on exponential Diophantine representation of enumerable
sets. Journal of Symbolic Logic 49 (1984), no. 3, 818-829.
[8] J. P. Jones, Yu. V. Matiyasevich. Proof of recursive unsolvability
of Hilbert's tenth problem. American Mathematical Monthly 98
(1991), no. 8, 689-709.
[9] G. J. Chaitin. Algorithmic Information Theory. Cambridge Tracts
in Theoretical Computer Science, volume 1. Cambridge University
Press, 1987.
[10] B. Poonen. Using elliptic curves of rank one towards the
undecidability of Hilbert's tenth problem over rings of algebraic
integers. In Algorithmic Number Theory (ANTS V), Lecture Notes
in Computer Science 2369, Springer, 2002, 33-42.
[11] J. H. Silverman. The Arithmetic of Elliptic Curves, 2nd edition.
Graduate Texts in Mathematics 106, Springer, 2009.
[12] E. Lucas. Sur les congruences des nombres euleriens et des
coefficients differentiels des fonctions trigonometriques
suivant un module premier. Bulletin de la Societe Mathematique
de France 6 (1878), 49-54.
[13] J. Robinson. Existential definability in arithmetic. Transactions
of the American Mathematical Society 72 (1952), no. 3, 437-449.
[14] D. Cantone, L. Cuzziol, E. G. Omodeo. On Diophantine singlefold
specifications. Le Matematiche 79 (2024), no. 2, 585-620.
[15] R. Miller, A. Shlapentokh. On existential definitions of c.e.
subsets of rings of functions of characteristic 0. Annals of
Pure and Applied Logic 173 (2022), no. 4, 103076.