Fixed-Prefix-State Construction Route For Size-2 Multi-Parallel Family Fails At Transition And Readout Submodularity

Claim/Theorem

Keep the notation of [[two-element-multi-parallel-circuit-family-satisfies-direct-fsep.md]], [[selected-or-selector-is-not-hidden-vertex-graph-cut-expressible.md]], and [[minimizing-hidden-binary-submodular-energy-preserves-submodularity.md]].

A natural recursive family-construction route for the size-2 connected multi-parallel family cannot realize ordinary hidden-vertex expressibility by fixed local submodular transition gadgets.

More precisely, let M_t be the size-2 multi-parallel family with

\[ f_t(x)=\lambda_{M_t}(L_x), \qquad x=(u,a_1,b_1,\dots,a_t,b_t)\in\{0,1\}^{2t+1}. \]

By [[two-element-multi-parallel-circuit-family-satisfies-direct-fsep.md]],

\[ f_t(x) = \sum_{i=1}^t \mathbf 1[a_i\ne b_i] + u\,\mathbf 1[\exists i:\ (a_i,b_i)=(0,0)] + (1-u)\,\mathbf 1[\exists i:\ (a_i,b_i)=(1,1)]. \]

So the most obvious recursive hidden-state route is:

1. realize the split count \sum_i \mathbf 1[a_i\ne b_i] locally;

2. scan the classes in order, maintaining prefix states

   \[ C_i=\mathbf 1[\exists j\le i:\ (a_j,b_j)=(1,1)], \qquad D_i=\mathbf 1[\exists j\le i:\ (a_j,b_j)=(0,0)]; \]

3. add the final readout

   \[ (1-u)C_t+uD_t. \]

If one tries to implement this route by fixed local binary-submodular gadgets, then the required transition and readout functions are already visibly non-submodular:

1. the full-prefix transition

   \[ T_{\mathrm{full}}(a,b,p,n):= \mathbf 1[n\ne p\vee(a\wedge b)] \]

   is not submodular;

2. the empty-prefix transition

   \[ T_{\mathrm{empty}}(a,b,p,n):= \mathbf 1[n\ne p\vee((1-a)(1-b))] \]

   is not submodular;

3. the final readout

   \[ R(u,c,d)=(1-u)c+ud \]

   is exactly the selected-OR selector from [[selected-or-selector-is-not-hidden-vertex-graph-cut-expressible.md]], hence is not hidden-vertex expressible at all.

Therefore this whole fixed-prefix-state recursive family-construction route fails. Any successful constructive theorem for the size-2 multi-parallel family must use either richer non-prefix global couplings or a larger hidden architecture not reducible to these local state-update gadgets.

Proof sketch:

1. The displayed formula for f_t shows that a prefix-state recursion would need the two OR-updates and the final selector readout.

2. For T_{\mathrm{full}}, take

   \[ x=(a,b,p,n)=(0,0,1,1), \qquad x'=(1,1,0,1). \]

   Then T_{\mathrm{full}}(x)=T_{\mathrm{full}}(x')=0, but for

   \[ x\wedge x'=(0,0,0,1), \qquad x\vee x'=(1,1,1,1), \]

   one gets

   \[ T_{\mathrm{full}}(x\wedge x')=1, \qquad T_{\mathrm{full}}(x\vee x')=0, \]

   violating submodularity.

3. For T_{\mathrm{empty}}, take

   \[ y=(0,0,0,1), \qquad y'=(0,1,0,0). \]

   Then T_{\mathrm{empty}}(y)=T_{\mathrm{empty}}(y')=0, but

   \[ y\wedge y'=(0,0,0,0), \qquad y\vee y'=(0,1,0,1) \]

   satisfy

   \[ T_{\mathrm{empty}}(y\wedge y')=1, \qquad T_{\mathrm{empty}}(y\vee y')=1, \]

   again violating submodularity.

4. The final readout R is exactly the selector already ruled out by [[selected-or-selector-is-not-hidden-vertex-graph-cut-expressible.md]].

5. By [[minimizing-hidden-binary-submodular-energy-preserves-submodularity.md]], any visible gadget required inside a binary-submodular hidden-vertex construction must itself be submodular. Hence none of these local fixed-state components can occur in such a realization.

Consequences for the current frontier:

• this closes a whole recursive family-construction pattern, not just one symmetric witness ansatz;
• the positive route cannot be reduced to bounded-state prefix accumulation over the parallel classes;
• the exact remaining constructive gap is therefore sharper: either non-prefix global coupling, or a genuinely richer auxiliary-state architecture with growth that is not implementable by fixed local update gadgets.

Dependencies

• [[two-element-multi-parallel-circuit-family-satisfies-direct-fsep.md]]
• [[selected-or-selector-is-not-hidden-vertex-graph-cut-expressible.md]]
• [[minimizing-hidden-binary-submodular-energy-preserves-submodularity.md]]

Conflicts/Gaps

• This node does not prove that the size-2 multi-parallel family is not ordinarily hidden-vertex representable.
• It rules out only the fixed-prefix-state recursive construction route with local state-update gadgets.
• More global constructions with richer hidden couplings or growing state remain open.

Sources

• 10.1016/j.dam.2009.07.001
• 10.1007/s10878-017-0136-y
• 10.48550/arXiv.2109.14599