8 The exact cost of an effective realization
On this page · Permalink · Source line 1
The selector does not change the completion, but it determines exactly which oracles can compute the original group. The proof must distinguish a named element from an unmarked isomorphism type.
8.1 Oracles, copies, and degrees
On this page · Permalink · Source line 5
An oracle for a set \(X\subseteq{\mathbb N}\) answers membership questions about \(X\). The notation \(A\le_T X\) means that a terminating oracle procedure decides membership in \(A\). Two sets have the same Turing degree when each is computable from the other.
The degree spectrum of a countable structure is the set of degrees of its copies. When that spectrum has a least degree, it is called the degree of the isomorphism type. This terminology is standard in computable structure theory [1], [2]. Here we prove an exact oracle criterion that specifies which oracles compute at least one copy. We do not identify this statement with an unproved claim that every such oracle degree is realized as the exact degree of a particular copy.
For a group on a countable coded domain, knowledge of its atomic diagram is equivalent, at the level needed here, to knowledge of its group operation and equality. A computation of integer multiples uses finitely many additions. A search for a root can therefore be performed in any oracle-computable copy.
8.2 A presentation from the selector
On this page · Permalink · Source line 12
Reduced rationals have canonical integer codes. Finite-support vectors in \(D\) have canonical codes given by increasing prime labels and nonzero residues. Their Cartesian product is a computably named countable domain with decidable equality and a computable bijection to \({\mathbb N}\).
Proposition 8.1: Uniform construction relative to the selector
If \(A\le_T X\), then the normal-form construction gives an \(X\)-computable copy of \(G_A\). In its canonical normal-form presentation, the group operation has Turing degree exactly \(\deg_T(A)\).
Proof
To add \((r,d)\) and \((t,e)\), compute the prime divisors of \({\operatorname{den}}(r){\operatorname{den}}(t)\). At each of these finitely many primes, query the corresponding selector bit and evaluate the three section residues. Lemma 5.2 guarantees that every other correction coordinate is zero. Formula (5.2) then gives the sum. Negation and equality are computable without querying \(A\).
For the lower bound on this particular presentation, compute the sum of the coded elements \((1/p,0)\) and \(((p-1)/p,0)\). Its finite torsion part is the value in Proposition 5.4. For \(p=p_{2n}\), that value is zero exactly when \(n\in A\). Thus the operation computes every selector bit.
The number of oracle questions used by one addition is finite and bounded by the number of distinct prime divisors of the denominator product. This is a locality statement about the operation, not a claim of a polynomial-time implementation. Factoring integers and finding their prime indices contribute ordinary computational costs.
8.3 Decoding a marked copy
On this page · Permalink · Source line 26
Proposition 8.2: Uniform marked decoding
Given an \(X\)-computable copy of \(G_A\) together with the name of \(u_A\), one can uniformly compute \(A\) in \(X\).
Proof
For input \(n\), search the domain simultaneously for solutions of
Each candidate test is decidable in \(X\). Exactly one equation has a solution by (6.2)–(6.3). Dovetailing the searches therefore terminates. A solution to the first equation means \(n\in A\), and a solution to the second means \(n\notin A\).
The procedure does not decide a negative existential statement directly. It uses two complementary positive searches. The paired selector is what converts enumerable root information into a total decision procedure.
8.4 Decoding an unmarked copy
On this page · Permalink · Source line 46
Theorem 8.3: Exact oracle criterion
For every \(A,X\subseteq{\mathbb N}\),
In particular, the isomorphism type of \(G_A\) has least presentation degree \(\deg_T(A)\).
Proof
The reverse implication is Proposition 8.1. For the forward implication, let \(H\) be an \(X\)-computable copy. Choose the name \(h\) of an infinite-order element. Such an element exists because \(H\) has quotient \({\mathbb Q}\) by its torsion subgroup.
Under an isomorphism to \(G_A\), the element \(h\) has a normal form with nonzero rational part. Lemma 7.1 gives a finite exception set. Choose \(N\) so that every prime in the pairs indexed by \(n\ge N\) avoids that set. For these \(n\), exactly one of
has a solution, and the first is solvable exactly when \(n\in A\).
Dovetailing the two searches decides every bit beyond \(N\). Hard-code the name of \(h\), the number \(N\), and the finitely many bits below \(N\) into the oracle procedure. These are finite constants, so the result is a Turing reduction of \(A\) to \(X\).
The canonical normal-form copy has exact degree \(\deg_T(A)\) by Proposition 8.1, while every copy computes \(A\) by the forward implication. Hence this degree is the least one.
There is no claim of a uniform algorithm finding an infinite-order element or its exception bound in every unmarked copy. The theorem is an existence statement about Turing reductions, and a finite list of constants is legitimate in such a reduction. For marked copies, Proposition 8.2 gives the genuinely uniform version.
The distinction also matches the algebra. If \(A{=^{*}} B\), then the unmarked groups are identical inside \(P\) and \(A\) and \(B\) have the same Turing degree. Recovering a literal selector uniformly from the unmarked group would demand more than the isomorphism type remembers.
8.5 Every degree over one computable completion
On this page · Permalink · Source line 73
Corollary 8.4: Degree variation with fixed observations
Every Turing degree occurs as the least presentation degree of a countable, reduced, residually finite abelian group whose profinite completion is \(P\), equipped with the fixed computable inverse-system presentation of Chapter 6.
Proof
Choose any set \(A\) of the desired degree and apply Theorem 8.3. All the structural and completion properties were proved in Chapters 4–6.
For \(A=\varnothing\), the copy is computable. For \(A=K\), the group has no computable copy and its least degree is the halting degree \(\mathbf 0'\). Iterated jumps yield further examples. An arbitrary selector supplies any desired degree without changing the finite quotient tables or their transition maps.
The group \(G_K\) still has a finite mathematical definition. Its noncomputability is not a proof that it cannot be named in a finite semantic language. The theorem concerns effective copies with computable operations and equality.
8.6 A sharper separation than prime-spectrum coding
On this page · Permalink · Source line 85
For the initial groups \(D_B\), an enumeration of the selected prime set suffices. For \(G_A\), the paired complementary tests decide the selector. Meanwhile, every prime torsion factor is present in every \(G_A\), so the information is no longer stored in which finite-order elements exist.
It resides in the relationship between torsion coordinates and infinite-order elements. All finite quotient groups remain fixed, but the root pattern of an admissible marked element distinguishes the selectors. This is why the construction measures a realization cost rather than merely relabeling the finite quotient data.