Claim 3 — operands of a target
ProvedCallCountPOPBR.claim_3addition-sequencescomputational-complexitynp-completenessp2o-gran-per-chapterp2o-plan-paperp2o-v1recursion
Let be a simple graph on vertices with edges, let , and let be a completion of under an admissible rule, with . Fix , let be the index of the target of , and let be any two earlier indices with . Then
- both indices lie before the target block: no earlier target is an operand, so the two values lie in (the base, chain and free values);
- one of them is a free node (an index ) whose value satisfies
where is the set of vertices such that has a set bit in and .
This is the soundness core of the reduction: every edge is served by a free node that touches only that edge's endpoints.
Differences from the source:
- encoding: V = {1, …, n} and a_v = sv → vertices 0, …, n − 1 of NPGraph.Graph with a_v = s(v + 1); reason: the published graph type numbers vertices from 0; the exponents are the same numbers s, 2s, …, ns
- reading: T_e = u + v with u, v available at the target of e; u, v ∈ P ∪ {F_1, …, F_K} → any two indices o₁, o₂ < t (t the target index of e_k in a completion) with E_{o₁} + E_{o₂} = T_{e_k} lie before the target block; one is a free index with the stated V-property; reason: the indices below t carry exactly the values in P, the F_k and the earlier targets, so these pairs are the page's pairs (u, v); the operands of the completion are one such pair
Preamble
import Definitions.Def_CallCountPOPBR_reductionInstance import Definitions.Def_CallCountPOPBR_IsAdmissibleRule import Definitions.Def_CallCountPOPBR_IsCompletion import Definitions.Def_CallCountPOPBR_Eval import Definitions.Def_CallCountPOPBR_Vset import Definitions.Def_CallCountPOPBR_redR set_option autoImplicit false
Formal statement
namespace CallCountPOPBR
/-- **Claim 3 (operands of a target).** Swain, *Recursive Call-Count Sequences: Structural Realisability, Periodic Branching, and
Partial-Observation Reconstruction*, STOC 2027 submission (manuscript sha256 79135884…), proof of Theorem 2.8, Claim 3, pp.6–7: "Let
e = {i, j} and suppose T_e = u + v with u, v available at the target of e, that is
u, v ∈ P ∪ {F_1, …, F_K} ∪ {T_{e′} : e′ earlier}. For w ∈ V let V(F) = {w ∈ V : F has a set bit
in [a_w − R, a_w]}. Then u, v ∈ P ∪ {F_1, …, F_K}, and one of u, v is a free node F with
∅ ≠ V(F) ⊆ {i, j}."
Let `G` be simple with `m ≥ 1` edges, `1 ≤ K ≤ n − 1`, and let `C` be a completion of `I(G, K)`
under an admissible rule. Let `t = d + a_z + K + k − 1` be the `k`-th target index (edge
`e_k = (i, j)`), and let `o₁, o₂ < t` be any two earlier indices with `E_{o₁} + E_{o₂} = T_{e_k}`.
Then both lie before the target block (no earlier target is an operand; the remaining indices are
the base, chain and free indices, whose `E`-values are `P ∪ {F_1, …, F_K}`), and one of them is a
free index `o` (`d + a_z ≤ o < d + a_z + K`) with `∅ ≠ V(E_o) ⊆ {i, j}`, where `R = 4n²`.
**Formalization Note.** The values `u, v` "available at the target of `e`" are the `E`-values of
the indices below `t`: those indices carry exactly `P ∪ {F_1, …, F_K} ∪ {T_{e′} : e′ earlier}`.
Quantifying over all such pairs, as the page does, covers the operand indices `t − a_t`, `t − b_t`
of the completion itself. -/
theorem claim_3 (G : NPGraph.Graph) (K : ℕ) (hG : NPGraph.IsSimple G) (hm : 1 ≤ numEdges G)
(hK : 1 ≤ K) (hKn : K + 1 ≤ G.order) (rule : ℕ → ℕ × ℕ) (C : ℕ → ℕ)
(hrule : IsAdmissibleRule (reductionInstance G K).d (reductionInstance G K).p rule)
(hC : IsCompletion (reductionInstance G K) rule C) (k : ℕ) (hk1 : 1 ≤ k)
(hkm : k ≤ numEdges G) (o₁ o₂ : ℕ)
(ho₁ : o₁ < L0 G K + zexp G.order + K + k - 1) (ho₂ : o₂ < L0 G K + zexp G.order + K + k - 1)
(hsum : Eval C o₁ + Eval C o₂ = target G.order ((edgeList G).getD (k - 1) (0, 0))) :
o₁ < L0 G K + zexp G.order + K ∧ o₂ < L0 G K + zexp G.order + K ∧
∃ o ∈ ({o₁, o₂} : Finset ℕ), L0 G K + zexp G.order ≤ o ∧ o < L0 G K + zexp G.order + K ∧
(Vset G.order (redR G.order) (Eval C o)).Nonempty ∧
Vset G.order (redR G.order) (Eval C o) ⊆
{((edgeList G).getD (k - 1) (0, 0)).1, ((edgeList G).getD (k - 1) (0, 0)).2} := by sorry
end CallCountPOPBR
Source
Swain, Recursive Call-Count Sequences: Structural Realisability, Periodic Branching, and Partial-Observation Reconstruction, STOC 2027 submission (manuscript sha256 79135884dd262e4297079b8d2f7adb5deec1b329582779ed16decf34adae2411), proof of Theorem 2.8, Claim 3, pp.6–7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.