Federated Assemblies

NEW RESULT — discrete: polynomial-time → continuous: polynomial-time · adversarial review: proved

Answer: Polynomial-time solvable; one independent uniform parameter suffices.

The anchor (named result in the paper)

statement extracted from the paper’s text layer; consult the paper for the exact wording

The continuous mirror question, as graded

Given a rooted laminar tree, rational masses of exact single-leaf types, and rational assembly mass $a$ with $M_v$ at least $a$, construct a randomized assignment of measurable sets $A_v$ of mass $a$ satisfying inheritance, pointwise inclusion probability $a/M_v$, and child intersection quota $a M_c/M_f$ both in expectation and in every realization.

Packaged proof task (what the prover saw — nothing else)

Given a finite rooted tree with $m$ nodes, a society is given by its support: the list of the $\tau$ exact single-leaf types with positive mass, each mass $b_\ell$ a binary rational. Here $\tau$ is the support size, not the number of possible types; require $\sum_\ell b_\ell=1$.
Realize each type as a disjoint atomless interval $X_\ell=\{\ell\}\times[0,b_\ell)$ with Lebesgue measure $\mu$. Define $X_v$ as the union of intervals at descendant leaves, including the leaf itself when $v$ is a leaf, and $M_v=\mu(X_v)$.
The common assembly mass $a$ is a binary rational satisfying $0<a\leq M_v$ for every node. Let $L$ be the total binary input length.
Construct jointly randomized measurable sets $A_v\subseteq X_v$. Every realization must satisfy $\mu(A_v)=a$, inheritance $A_f\subseteq\bigcup_{c\in\operatorname{children}(f)}A_c$, and $\mu(A_f\cap A_c)=aM_c/M_f$ for every parent–child pair $(f,c)$.
Require $\Pr[x\in A_v]=a/M_v$ for every $x\in X_v$, and $\mathbb E[\mu(A_f\cap A_c)]=aM_c/M_f$.
Represent the output by finite arithmetic and comparison circuits with binary rational constants defining membership in each $A_v$ from a person's leaf and interval coordinate and finitely many independent uniform parameters in $[0,1)$. The circuits must be defined for every parameter value; complexity means Turing time to construct this symbolic description.

Is this exact randomized construction problem solvable in polynomial time in $m,\tau,L$, or is it NP-hard?

Discrete laminar instances admit a polynomial-time randomized algorithm satisfying inheritance, equal individual inclusion probabilities, expected proportional child representation, and ex post child quotas rounded down ([Halpern et al., Federated Assemblies](https://daniel-halpern.com/files/federated-assemblies.pdf)).
No result settling this exact atomless construction problem was located in the literature search.

Modeling choices made when packaging the task

Prover output (gpt-6.1-sol / high, Bolzano prover prompt)

Result

The exact randomized construction problem is polynomial-time solvable. One uniform random parameter suffices. The construction guarantees, in every realization, proportional representation of every individual leaf within every ancestor assembly.

1. Construction

Let $\mathcal S$ be the supplied support of positive-mass leaves. For each node $v$, define

\[ p_v=\frac{a}{M_v}. \]

The hypotheses imply $0<p_v\leq 1$. If $c$ is a child of $f$, then $X_c\subseteq X_f$, so $M_c\leq M_f$ and consequently $p_f\leq p_c$.

Draw one uniform parameter $U\in[0,1)$. For $t,u\in[0,1)$, define the circular translation

\[ R_u(t)= \begin{cases} t-u,&t\geq u,\\ t-u+1,&t<u. \end{cases} \]

Thus $R_u(t)\in[0,1)$, including at all boundary values.

For each node $v$, set

\[ A_v(u)= \left\{(\ell,x)\in X_v: R_u\!\left(\frac{x}{b_\ell}\right)<p_v \right\}. \]

All nodes use the same parameter $u$. The sets are measurable because their membership predicates use finitely many arithmetic operations and comparisons.

2. Exact masses in every realization

Fix $u\in[0,1)$ and $p\in(0,1]$. Directly from the definition,

\[ \{t\in[0,1):R_u(t)<p\} = [u,\min\{u+p,1\}) \;\cup\; [0,\max\{u+p-1,0\}). \]

These half-open intervals are disjoint. Their total length is

\[ \min\{p,1-u\}+\max\{u+p-1,0\}=p. \]

Indeed, if $u+p\leq1$, the two terms are $p$ and $0$; otherwise they are $1-u$ and $u+p-1$.

Scaling by $b_\ell$, every supported descendant leaf $\ell$ of $v$ therefore satisfies

\[ \mu(A_v(u)\cap X_\ell)=b_\ell p_v. \]

This equality holds for every parameter value. Summing over the disjoint descendant leaf intervals gives

\[ \mu(A_v(u)) = p_v\sum_{\ell\text{ descendant of }v}b_\ell = p_vM_v = a. \]

The defining restriction also gives $A_v(u)\subseteq X_v$.

3. Inheritance and exact child quotas

Fix a parent–child pair $(f,c)$. Since $p_f\leq p_c$, any $(\ell,x)\in A_f(u)\cap X_c$ satisfies

\[ R_u(x/b_\ell)<p_f\leq p_c. \]

Hence

\[ A_f(u)\cap X_c\subseteq A_c(u). \]

Every descendant leaf of an internal node belongs to exactly one child subtree. Applying this inclusion to each child proves inheritance:

\[ A_f(u)\subseteq \bigcup_{c\in\operatorname{children}(f)}A_c(u). \]

Furthermore, $A_c(u)\subseteq X_c$, so the preceding inclusion implies the exact set identity

\[ A_f(u)\cap A_c(u)=A_f(u)\cap X_c. \]

Using the leafwise mass calculation from Section 2,

\[ \mu(A_f(u)\cap A_c(u)) = \sum_{\ell\text{ descendant of }c}b_\ell p_f = M_cp_f = \frac{aM_c}{M_f}. \]

Thus every required child quota holds in every realization. Its expected value is consequently also $aM_c/M_f$.

4. Inclusion probability of every individual

Fix an actual person $(\ell,x)\in X_v$, and write $t=x/b_\ell\in[0,1)$.

As a function of $u$, the map $R_u(t)$ is

\[ R_u(t)= \begin{cases} t-u,&0\leq u\leq t,\\ t-u+1,&t<u<1. \end{cases} \]

The first branch maps $[0,t]$ bijectively onto $[0,t]$; the second maps $(t,1)$ bijectively onto $(t,1)$. Each branch preserves Lebesgue measure because it is a translation composed with reflection. The images partition $[0,1)$. Therefore $R_U(t)$ is uniform on $[0,1)$.

It follows that

\[ \Pr[(\ell,x)\in A_v(U)] = \Pr[R_U(t)<p_v] = p_v = \frac{a}{M_v}. \]

This argument applies to every fixed person, including $x=0$; it is not merely an almost-everywhere statement.

5. Polynomial-size circuit representation

Assign the supported leaves distinct integer identifiers. For a queried leaf identifier $\ell$, let $\delta_j$ be the comparison bit indicating $\ell=j$.

Precompute the binary rational constants

\[ \beta_j=\frac{1}{b_j}, \qquad p_v=\frac{a}{M_v}. \]

For a valid person, the normalized coordinate is computed by

\[ t=x\sum_{j\in\mathcal S}\delta_j\beta_j. \]

Exactly one $\delta_j$ equals $1$, so this gives $t=x/b_\ell$. Next compute

\[ e=\mathbf 1[t<U], \qquad r=t-U+e. \]

Thus $r=R_U(t)$. No remainder operation or division by a variable is needed.

Let $D_v$ indicate that the input leaf is a descendant of $v$. This can be computed from the leaf comparison bits and the tree: at a leaf use its corresponding bit, and at an internal node take the Boolean disjunction of its children’s indicators. The membership output for $A_v$ is

\[ D_v\;\wedge\;(r<p_v). \]

Boolean conjunction and disjunction can themselves be implemented arithmetically on comparison bits, using $xy$ and $x+y-xy$, respectively.

With shared gates, the whole description has $O(m+\tau)$ arithmetic and comparison gates, apart from the encodings of its constants and connections. Even duplicating the shared calculations into separate membership circuits gives polynomial total size. The circuits are defined for every $U\in[0,1)$, including equality cases.

It remains to check the bit lengths of the constants. Write the input masses as $b_j=n_j/d_j$, and let $D=\prod_jd_j$. The binary length of $D$ is $O(L)$. Every node mass can be written as

\[ M_v=\frac{N_v}{D}, \qquad 0<N_v\leq D, \]

because it sums a subset of positive masses whose total is $1$. Thus its numerator and denominator have $O(L)$ bits. Writing $a=A/B$, we may encode

\[ p_v=\frac{AD}{BN_v}. \]

These constants, and the reciprocals $\beta_j$, likewise have $O(L)$-bit encodings. Tree traversal and exact arithmetic on these integers take polynomial Turing time.

Hence the complete symbolic description is constructible in polynomial time in $m,\tau,L$, with no expansion into a number of pieces proportional to the denominators.

⟨structured verdict parsed — rendered above⟩

Adversarial review (gpt-6.1-sol / medium, Bolzano verifier prompt)

The prover resolves the assigned problem. The construction is correct for every permitted parameter value, gives the required probabilities for every person, and admits the claimed polynomial-time symbolic representation. I found no mathematical or complexity gap.

Here, “binary rational” is read as a rational represented by binary-encoded numerator and denominator, consistently with the prover’s encoding analysis.

Definitions and domain restrictions. Every supported mass $b_\ell$ is positive, so $x/b_\ell$ is defined and lies in $[0,1)$ for every actual person. The assumption $0<a\leq M_v$ ensures that every $M_v$ is positive and that $0<p_v\leq1$. For each parent–child pair, $M_c\leq M_f$, hence $p_f\leq p_c$. All these conclusions follow directly from the task’s hypotheses.

Circular translation and exact masses. The two branches defining $R_u(t)$ produce values in $[0,1)$, including when $t=u$. The stated inverse image of $[0,p)$ is correct:

$$ [u,\min\{u+p,1\})\;\cup\;[0,\max\{u+p-1,0\}). $$
The intervals are disjoint and their lengths sum to $p$. This also covers $u=0$, $u+p=1$, and $p=1$. Scaling by $b_\ell$ therefore gives leafwise mass $b_\ell p_v$ for every realization. Summing over supported descendant leaves gives $\mu(A_v(u))=p_vM_v=a$. Restricting the definition to $X_v$ supplies the required containment.

Inheritance. For a person in $A_f(u)\cap X_c$, the inequality $R_u(x/b_\ell)<p_f\leq p_c$ proves membership in $A_c(u)$. The child subtrees partition the descendant leaves of an internal node, so this implication establishes the required inheritance inclusion. It is a pointwise set inclusion, with no exceptional null set.

Exact child quotas and their expectations. Together with $A_c(u)\subseteq X_c$, the preceding inclusion proves the asserted identity $A_f(u)\cap A_c(u)=A_f(u)\cap X_c$. The leafwise mass formula then gives

$$ \mu(A_f(u)\cap A_c(u))=p_fM_c=\frac{aM_c}{M_f}. $$
This holds for every parameter value. Consequently, its expectation has precisely the required value.

Every-person inclusion probabilities. For fixed $t\in[0,1)$, the two branches of $u\mapsto R_u(t)$ map $[0,t]$ onto $[0,t]$ and $(t,1)$ onto $(t,1)$, respectively. Both preserve Lebesgue measure, and their images partition $[0,1)$. Thus $R_U(t)$ is uniform. The inclusion probability is $p_v=a/M_v$ for every fixed person, including $x=0$. The argument proves the stated pointwise requirement, rather than merely an almost-everywhere version.

Measurability and circuit representation. The predicates use finite arithmetic operations and comparisons, so they are measurable jointly in the coordinate and random parameter. For a valid person, exactly one leaf comparison bit is $1$, making the normalization formula correct. The comparison $t<U$ selects the correct circular-translation branch, including equality. Descendant indicators and their Boolean combinations correctly restrict membership to $X_v$. No operation divides by a variable or becomes undefined at any permitted parameter value. One uniform parameter is sufficient; the independence requirement imposes no additional condition on a single parameter.

Polynomial construction time. The common denominator $D=\prod_jd_j$ has bit length bounded by the sum of the input denominator lengths, hence $O(L)$. Each node mass has an integer numerator $N_v$ satisfying $0<N_v\leq D$. The encodings of $p_v=AD/(BN_v)$ and $\beta_j=d_j/n_j$ therefore have $O(L)$ bits. The shared circuit uses $O(m+\tau)$ gates; connection encodings, constant encodings, and even duplication into separate membership circuits remain polynomial in $m,\tau,L$. Computing these data by tree traversal and exact integer arithmetic also takes polynomial Turing time.

The stronger claimed leafwise proportionality is established by the same exact mass calculation. No cited external theorem is needed for the conclusion.