Representative Committees of Peers (d4-journals-jair-2021-0041)

Given \(m\), \(k\), a finite explicit type set \(T\subseteq\{0,1\}^{m}\), and rational masses \(\mu_x\) summing to \(1\), compute \(R_k(\mu)=\mathbb{E}[SC_\mu(Z)]/\min_{z\in\{0,1\}^{m}}SC_\mu(z)\), where \(k\) types are sampled independently from \(\mu\), \(Z\) is their coordinate-wise majority with uniform tie-breaking, and \(SC_\mu(z)=\sum_{x\in T}\mu_x d_H(x,z)\); in the robust version, determine \(R_k^\star=\sup_{m,T,\mu}R_k(\mu)\) and an \(\varepsilon\)-optimal rational witness.

Let \(m,k\geq1\) be integers. A society is given by its support \(T\subseteq\{0,1\}^{m}\): the list of its \(\tau=|T|\) types with positive binary-rational masses \(\mu_x\), summing to \(1\). Support size means the number of listed types, not \(2^m\).
Draw \(k\) types independently from \(\mu\), counting repeated draws separately. Let \(Z\) be their coordinate-wise majority, with independent fair tie-breaking on tied coordinates.
Define \(SC_\mu(z)=\sum_{x\in T}\mu_x d_H(x,z)\) using Hamming distance, and \(R_k(\mu)=\mathbb E[SC_\mu(Z)]/\min_{z\in\{0,1\}^{m}}SC_\mu(z)\); set \(0/0=1\).
Define \(R_k^\star=\sup_{m,T,\mu}R_k(\mu)\), over all such societies. For rational \(0<\varepsilon<1\), an \(\varepsilon\)-optimal witness is a finite rational society \(\widehat\mu\) with \(R_k(\widehat\mu)\geq R_k^\star-\varepsilon\).
Encode integers in binary; let \(L\) be total input bit length. Express running times in \(m,\tau,L,k\) and, where applicable, \(\varepsilon\), including witness output size.

What is the sharp worst-case approximation ratio \(R_k^\star\) as a function of \(k\), and how efficiently can \(R_k(\mu)\), an additive-\(\varepsilon\) estimate of \(R_k^\star\), and an \(\varepsilon\)-optimal rational witness be computed?

For finite populations, uniform sampling without replacement and majority voting have approximation ratio at most \(1+6e^{-1/2}/\sqrt{k}\), with matching asymptotic order when population size is sufficiently large. [Verified source](https://www.jair.org/index.php/jair/article/download/12521/26694/27514).
No result settling the full independent-sampling evaluation and sharp-ratio task was located in the literature search.

Sharp ratio

Put \(n=k\) when \(k\) is odd and \(n=k-1\) when \(k\) is even, and write \(n=2r+1\). Define

\( \displaystyle q_n(p)=\sum_{j=r+1}^{n}\binom nj p^j(1-p)^{n-j},\qquad 0\le p\le \frac12. \)

Then the sharp answer is

\( \displaystyle R_k^\star=\sup_{0<p\le 1/2}\left[1+\frac{1-2p}{p}q_n(p)\right]. \)

This univariate characterization has a unique maximizing point when \(n\ge3\):

• \(R_1^\star=R_2^\star=2\). This supremum is not attained.
• For \(n\ge3\), let \(p_n\) be the unique solution in \((0,1/2)\) of

\(p(1-2p)q_n'(p)=q_n(p)\). Then
\(R_k^\star=1+(1-2p_n)q_n(p_n)/p_n\).

• In particular,

\( \displaystyle R_3^\star=R_4^\star=\frac{17+7\sqrt7}{27}=1.315565\ldots. \)

• As \(k\to\infty\),

\( \displaystyle R_k^\star=1+\frac{C}{\sqrt{k}}+o(k^{-1/2}), \)
where
\( \displaystyle C=\max_{a\ge0}2a\Phi(-a)=0.3399424\ldots. \)

Here \(\Phi\) is the standard normal distribution function.

Exact evaluation is polynomial in \(m,\tau,k,L\), with explicit rational output of \(O(kL+\log(m+1))\) bits. Its dependence on the numerical value of binary-encoded \(k\) cannot generally be removed: even fixed dyadic masses can produce an exact answer requiring \(\Omega(k)\) bits.

An additive-\(\varepsilon\) estimate of \(R_k^\star\), together with an \(\varepsilon\)-optimal rational witness, can be computed in time polynomial in \(L\) and \(1/\varepsilon\). The witness always needs only \(m=1\), \(\tau=2\), and \(O(1+\log(1/\varepsilon))\) output bits.

The [cited finite-population paper](https://www.jair.org/index.php/jair/article/download/12521/26694/27514) analyzes sampling without replacement. The proof below treats independent draws directly.

1. Reduction to one coordinate

For each coordinate \(i\), define

\( \displaystyle u_i=\sum_{x\in T}\mu_xx_i,\qquad p_i=\min\{u_i,1-u_i\}. \)

Choosing a coordinate value independently of all other coordinates minimizes social cost, so

\( \displaystyle \min_z SC_\mu(z)=\sum_{i=1}^m p_i. \)

After complementing a coordinate if necessary, its minority value is \(1\), with probability \(p_i\). Across the independently sampled types, the votes in this coordinate are independent Bernoulli variables with parameter \(p_i\). Dependence between different coordinates does not affect the expectation of their sum.

Even sample sizes. Consider \(2s\) votes and delete a uniformly random vote. If there was a strict majority, deleting one vote preserves its outcome. If there was a tie, either resulting majority occurs with probability \(1/2\). The remaining \(2s-1\) votes are independently distributed Bernoulli votes. Consequently, fair majority with \(2s\) votes has exactly the same probability of choosing either coordinate value as majority with \(2s-1\) votes.

Thus the probability of selecting the minority value is \(q_n(p_i)\). The expected cost of coordinate \(i\) is

\( \displaystyle p_i+(1-2p_i)q_n(p_i). \)

If \(P=\sum_i p_i>0\), define, for \(p>0\),

\( \displaystyle \rho_n(p)=1+\frac{1-2p}{p}q_n(p). \)

Then

\( \displaystyle R_k(\mu)= \frac{\sum_{i:p_i>0}p_i\rho_n(p_i)}{\sum_i p_i}. \)

This is a weighted average of one-coordinate ratios. Hence it is at most \(\sup_{0<p\le1/2}\rho_n(p)\).

Conversely, every rational \(p\in(0,1/2]\) is realized by the one-dimensional society

\( \displaystyle T=\{0,1\},\qquad \mu_0=1-p,\qquad \mu_1=p, \)

whose ratio is \(\rho_n(p)\). Rational, and indeed dyadic, points are dense, and \(\rho_n\) is continuous on \((0,1/2]\). This proves the asserted supremum formula.

If \(P=0\), every coordinate is constant on the positive-mass support. The sampled outcome has zero cost, and the prescribed ratio is \(1\).

2. The unique maximizing marginal

For \(n=1\), \(q_1(p)=p\), so

\( \displaystyle \rho_1(p)=2-2p. \)

Its supremum is \(2\), approached as \(p\downarrow0\). Every positive-cost finite society has ratio strictly below \(2\), by the weighted-average formula; a zero-cost society has ratio \(1\).

Now suppose \(r\ge1\). Put \(F_n(p)=\rho_n(p)-1\). Since \(q_n(p)=O(p^{r+1})\), the function extends continuously to \(p=0\) with \(F_n(0)=0\). Also \(F_n(1/2)=0\), and \(F_n(p)>0\) on \((0,1/2)\).

Differentiating the binomial sum and cancelling adjacent terms gives

\( \displaystyle q_n'(p)=n\binom{2r}{r}p^r(1-p)^r. \)

Let

\( \displaystyle H(p)=p(1-2p)q_n'(p)-q_n(p). \)

Direct differentiation yields

\( \displaystyle F_n'(p)=\frac{H(p)}{p^2}, \)

and

\( \displaystyle H'(p) =q_n'(p)\left[\frac{r(1-2p)^2}{1-p}-4p\right] =\frac{q_n'(p)}{1-p}\left[r-4(r+1)p(1-p)\right]. \)

Because \(p(1-p)\) increases strictly on \((0,1/2)\), the last bracket changes sign exactly once, at

\( \displaystyle a_r=\frac{1-(r+1)^{-1/2}}2. \)

Therefore \(H\) increases strictly on \((0,a_r)\) and decreases strictly on \((a_r,1/2)\). Its endpoint values are

\( \displaystyle H(0)=0,\qquad H(1/2)=-q_n(1/2)=-\frac12. \)

It follows that \(H\) has exactly one zero \(p_n\) in \((a_r,1/2)\). Moreover, \(F_n'\) is positive before \(p_n\) and negative afterward. This proves that \(p_n\) is the unique global maximizer.

The characterization is algebraic: \(H(p)\) is an integer polynomial divisible by \(p^{r+1}\), and \(H(p)/p^{r+1}\) has degree at most \(r+1\).

For \(n=3\),

\( \displaystyle F_3(p)=3p-8p^2+4p^3,\qquad p_3=\frac{4-\sqrt7}{6}, \)

which gives the stated value of \(R_3^\star=R_4^\star\).

A useful additional identity is

\( \displaystyle q_{2r+1}(p)-q_{2r-1}(p) =\binom{2r-1}{r}p^r(1-p)^r(2p-1). \)

To verify it, condition on the first \(2r-1\) votes. Adding two votes changes the outcome only when the original count of ones is \(r-1\) or \(r\): the respective changes have probabilities \(p^2\) and \(-(1-p)^2\). Substitution gives the identity.

Thus \(q_n(p)\le p\) for \(p\le1/2\), and all ratios are at most \(2\). The sharp ratios decrease strictly along odd sample sizes, with each value repeated at the following even size.

3. A uniform bound and the sharp asymptotic constant

For \(r\ge1\) and \(p>0\), the identity \(\binom nj=(n/j)\binom{n-1}{j-1}\) gives

\( \displaystyle \frac{q_n(p)}p \le \frac{n}{r+1}\Pr\{\operatorname{Bin}(2r,p)\ge r\}. \)

For \(p\le1/2\), apply the exponential Markov inequality with
\(\lambda=\log((1-p)/p)\). Its right-hand side is

\( \displaystyle e^{-\lambda r}(1-p+pe^\lambda)^{2r} =[4p(1-p)]^r. \)

Writing \(\delta=1-2p\), we obtain

\( \displaystyle F_n(p)\le2\delta(1-\delta^2)^r. \)

The maximum of \(\delta(1-\delta^2)^r\) on \([0,1]\) occurs at \(\delta=1/\sqrt{2r+1}=1/\sqrt n\): its derivative has the sign of \(1-n\delta^2\). In particular,

\( \displaystyle 0\le R_k^\star-1\le\frac2{\sqrt n}. \)

This also holds for \(n=1\).

For the sharp asymptotic, define

\( \displaystyle w_n(s)= \begin{cases} (1-s^2/n)^{(n-1)/2},&0\le s\le\sqrt n,\\ 0,&s>\sqrt n, \end{cases} \qquad I_n=\int_0^\infty w_n(s)\,ds. \)

Integrating the formula for \(q_n'\), changing variables, and using \(q_n(1/2)=1/2\) gives

\( \displaystyle q_n\!\left(\frac{1-a/\sqrt n}{2}\right) =\frac{\int_a^\infty w_n(s)\,ds}{2I_n}, \qquad 0\le a\le\sqrt n. \)

For each fixed \(s\), \(w_n(s)\to e^{-s^2/2}\). For all odd \(n\ge3\),

\( \displaystyle 0\le w_n(s)\le e^{-s^2/3}. \)

Indeed, on its nonzero domain this follows from
\(\log(1-x)\le-x\) and \((n-1)/(2n)\ge1/3\). The dominating function is integrable. Dominated convergence therefore gives

\( \displaystyle I_n\longrightarrow\sqrt{\pi/2},\qquad \int_0^\infty|w_n(s)-e^{-s^2/2}|\,ds\longrightarrow0. \)

Consequently, uniformly for \(a\) in every fixed compact interval,

\( \displaystyle q_n\!\left(\frac{1-a/\sqrt n}{2}\right)\longrightarrow\Phi(-a), \)

and hence

\( \displaystyle G_n(a):=\sqrt n\,F_n\!\left(\frac{1-a/\sqrt n}{2}\right) \longrightarrow 2a\Phi(-a). \)

At \(a=\sqrt n\), define \(G_n(a)=0\), consistently with \(F_n(0)=0\). The preceding uniform bound also gives, throughout the domain,

\( \displaystyle 0\le G_n(a)\le2a e^{-a^2/3}. \)

This upper bound tends to zero as \(a\to\infty\), uniformly in \(n\). Uniform convergence on compact intervals and this uniform tail bound imply convergence of the maxima:

\( \displaystyle \sqrt n\,(R_k^\star-1)\longrightarrow C=\max_{a\ge0}2a\Phi(-a). \)

For completeness, this limiting maximizer is unique. Let
\(\phi(a)=e^{-a^2/2}/\sqrt{2\pi}\) and
\(g(a)=\Phi(-a)-a\phi(a)\). Then

\( \displaystyle g'(a)=(a^2-2)\phi(a). \)

Thus \(g\) decreases strictly on \([0,1]\). Also \(g(0)=1/2\), whereas, for \(a>0\),

\( \displaystyle \Phi(-a)<\frac{\phi(a)}a, \)

because replacing the integrand \(\phi(t)\) by \(t\phi(t)/a\) strictly increases its integral over \((a,\infty)\). Hence \(g(1)<0\), and \(g(a)<0\) for every \(a\ge1\).

The unique maximizer \(a_\star\in(0,1)\) therefore satisfies
\(\Phi(-a_\star)=a_\star\phi(a_\star)\). Numerically,
\(a_\star=0.7517915\ldots\) and \(C=0.3399424\ldots\).
Finally, \(n/k\to1\), proving the stated asymptotic in \(k\).

4. Exact evaluation and output size

Use the conventional encoding of rationals by explicitly written binary numerators and denominators. Take a common denominator \(D\) for the masses; the product of their denominators suffices and has \(O(L)\) bits. Write \(\mu_x=w_x/D\).

Compute

\( \displaystyle b_i=\min\left\{\sum_xw_xx_i,\ D-\sum_xw_xx_i\right\}, \qquad B=\sum_i b_i. \)

These require \(O(m\tau)\) integer additions after constructing the \(w_x\). If \(B=0\), return \(1\). Otherwise set

\( \displaystyle S_i=\sum_{j=r+1}^{n}\binom nj b_i^j(D-b_i)^{n-j}. \)

The exact answer is

\( \displaystyle R_k(\mu)= \frac{BD^n+\sum_i(D-2b_i)S_i}{BD^n}. \)

Each \(S_i\) can be computed in \(O(n)\) integer arithmetic steps. Start with \(t_0=(D-b_i)^n\), and use

\( \displaystyle t_{j+1}= \frac{t_j(n-j)b_i}{(j+1)(D-b_i)}. \)

Every division is exact, since \(t_j=\binom njb_i^j(D-b_i)^{n-j}\). Sum the terms with \(j\ge r+1\).

All intermediate integers have
\(O((n+1)L+\log(m+1))\) bits. Using schoolbook integer arithmetic gives the conservative bit-time bound

\( \displaystyle O\!\left((m\tau+mn)\big((n+1)L+\log(m+1)\big)^2\right). \)

The explicit rational output has
\(O((n+1)L+\log(m+1))=O(kL+\log(m+1))\) bits.

An unavoidable output obstruction. Fix the dyadic society with minority mass \(1/4\). Take \(r=2^t\) and \(n=2r+1\), and let \(S_j=4^j q_j(1/4)\) for odd \(j\). The tail identity above gives

\( \displaystyle S_n=16S_{n-2}-2\binom{2r-1}{r}3^r. \)

The coefficient \(\binom{2r-1}{r}\) is odd: over the field with two elements,

\( \displaystyle (1+X)^{2r-1}=1+X+\cdots+X^{2r-1}, \)

as follows by multiplying both sides by \(1+X\) and using
\((1+X)^{2r}=1+X^{2r}\). Therefore \(S_n\equiv2\pmod4\).

For this society,

\( \displaystyle \rho_n(1/4)=1+\frac{2S_n}{4^n}. \)

Its numerator \(4^n+2S_n\) is divisible by \(4\) and not by \(8\). Its reduced denominator is consequently \(2^{2n-2}\), requiring \(\Omega(n)\) bits. Here the input length is only \(O(\log n)\). Thus exact, explicitly written rational evaluation cannot run in time polynomial in binary input length alone.

5. Certified estimates and rational witnesses

Here \(L\) includes the encoding of \(\varepsilon\). All logarithms below are base two.

First, if \(n\ge4/\varepsilon^2\), return the estimate \(1\) and the balanced two-type witness \(\mu_0=\mu_1=1/2\). Its ratio is exactly \(1\), and Section 3 proves both required guarantees.

For \(n=1\), return the exact estimate \(2\). Choose

\( \displaystyle b=\left\lceil\log(2/\varepsilon)\right\rceil,\qquad \mu_1=2^{-b},\qquad \mu_0=1-2^{-b}. \)

Its ratio is \(2-2^{1-b}\ge2-\varepsilon\).

It remains to handle \(3\le n<4/\varepsilon^2\).

A proved continuity bound. From
\(\binom{2r}{r}\le4^r\) and \(p(1-p)\le1/4\),

\( \displaystyle \frac{q_n'(p)}p =n\binom{2r}{r}p^{r-1}(1-p)^r\le4n. \)

Integrating \(q_n'(p)\le4np\) gives \(q_n(p)\le2np^2\). Therefore

\( \displaystyle |F_n'(p)| =\left|\frac{(1-2p)q_n'(p)}p-\frac{q_n(p)}{p^2}\right| \le6n. \)

The continuous extension of \(F_n\) is consequently \(6n\)-Lipschitz on \([0,1/2]\).

Bisect the interval \([0,1/2]\), evaluating the sign of \(H\) exactly at each midpoint. Section 2 proves that a positive sign puts the midpoint below \(p_n\), and a negative sign puts it above \(p_n\). If the sign is zero, an exact rational maximizer has been found.

Otherwise perform

\( \displaystyle t=\left\lceil\log(6n/\varepsilon)\right\rceil \)

bisections and take the final midpoint \(\widehat p\). Its distance from \(p_n\) is at most \(2^{-(t+2)}\), so

\( \displaystyle 0\le R_k^\star-\rho_n(\widehat p) \le6n\,2^{-(t+2)} \le\varepsilon/4. \)

Return the witness with masses \(\widehat p\) and \(1-\widehat p\). Compute \(\rho_n(\widehat p)\) exactly and round it downward to a dyadic grid of spacing at most \(\varepsilon/4\). The resulting estimate differs from \(R_k^\star\) by at most \(\varepsilon/2\).

At each bisection step, the integers have \(O(nt)\) bits, and the binomial tail and derivative require \(O(n)\) arithmetic steps. Thus a conservative bit-time bound is

\( \displaystyle O(L^2+n^3t^3). \)

Since this branch has \(n<4/\varepsilon^2\), the overall algorithm runs in

\( \displaystyle O\!\left(L^2+\varepsilon^{-6} (1+\log(1/\varepsilon))^3\right). \)

Both the rounded estimate and the witness have
\(O(1+\log(1/\varepsilon))\) output bits. The witness always has exactly two positive dyadic masses, in one dimension.

The same cutoff also yields additive-\(\varepsilon\) evaluation of a given society in time polynomial in its input length and \(1/\varepsilon\): return \(1\) above the cutoff, and otherwise evaluate the exact formula and round.

⟨structured verdict parsed — rendered above⟩

Verification report

The prover resolves the task. The sharp-ratio characterization, uniqueness claim, asymptotic constant, exact-evaluation algorithm, output-size obstruction, and approximation and witness algorithms are correct. I found no major or minor issues requiring repair.

The complexity claims must retain their stated parameters: exact evaluation is polynomial in the numerical value of \(k\), whereas the approximation algorithms are polynomial in \(L\) and \(1/\varepsilon\).

1. Reduction to one coordinate

The coordinate marginal \(u_i\) and minority probability \(p_i\) are correctly defined. Hamming cost is additive across coordinates, and minimizing each coordinate separately gives
\[ \min_z SC_\mu(z)=\sum_i p_i. \]

The independent type draws yield independent Bernoulli votes within each coordinate. Dependence between coordinates does not invalidate the expected-cost calculation, which uses linearity of expectation.

The deletion argument for even sample sizes is valid:

• A strict majority among \(2s\) votes survives deletion of one vote.
• From a tie, uniformly deleting one vote gives either resulting majority with probability \(1/2\).
• Uniformly deleting an index independently of the votes leaves \(2s-1\) independent votes with the original marginal distribution.

Only the coordinate outcome probabilities are needed; joint equivalence across coordinates is unnecessary.

The expected coordinate cost
\[ p_i+(1-2p_i)q_n(p_i) \]
is correct. Coordinates with \(p_i=0\) contribute zero, so the weighted-average formula correctly omits them.

Every admissible rational one-coordinate marginal is realized by the stated two-type society. Dyadic density and continuity justify equality of the society supremum and the univariate supremum, even if “binary-rational” is restricted to dyadic masses.

The zero-denominator case is also handled correctly: positive masses and zero minority probabilities force each coordinate to be constant throughout the support, so both costs vanish and the prescribed ratio is \(1\).

2. Maximization and small sample sizes

For \(n=1\), the calculation \(\rho_1(p)=2-2p\) is correct. It establishes supremum \(2\), its nonattainment, and consequently both claims for \(k=1,2\).

For \(r\geq1\), the endpoint extension \(F_n(0)=0\) follows from \(q_n(p)=O(p^{r+1})\). Both endpoint values and interior positivity are correct.

The derivative identities check out:
\[ q_n'(p)=n\binom{2r}{r}p^r(1-p)^r, \]
\[ F_n'(p)=\frac{H(p)}{p^2}, \qquad H'(p)=\frac{q_n'(p)}{1-p} \left[r-4(r+1)p(1-p)\right]. \]

The sign-changing bracket has exactly the stated root \(a_r\). Since \(q_n'(p)>0\) on the interior, the asserted strict increase and decrease of \(H\) follow. Together with \(H(0)=0\) and \(H(1/2)=-1/2\), this establishes precisely one interior zero and the unique global maximizer.

The polynomial divisibility and degree claims are correct.

The calculation for \(n=3\) is correct. Independent numerical checking gives
\[ p_3\approx0.2257081148, \qquad R_3^\star\approx1.3155651547, \]
consistent with the stated exact expression and decimal.

The neighboring-tail identity has the correct coefficient and sign. It establishes \(q_n(p)\leq p\) and strict decrease of the sharp ratios along odd sample sizes. The even-size equivalence establishes the repeated values.

3. Uniform bound and asymptotic constant

The binomial-coefficient inequality correctly bounds \(q_n(p)/p\) by the stated binomial tail. The exponential Markov calculation is valid for \(0<p\leq1/2\), including \(p=1/2\), where the chosen exponent is zero.

The resulting bound
\[ F_n(p)\leq2\delta(1-\delta^2)^r \]
and its maximization at \(\delta=1/\sqrt n\) are correct. The weaker bound \(R_k^\star-1\leq2/\sqrt n\) follows, with \(n=1\) separately covered by the preceding exact result.

The integral representation using \(w_n\) has the correct normalization and change of variables. For odd \(n\geq3\), the proposed integrable dominating function bounds \(w_n\) throughout its domain. Thus both dominated-convergence conclusions are justified.

The convergence of the normalized tail probabilities is uniform on compact intervals. The subsequent convergence of \(G_n\) is valid because its remaining factor converges uniformly on those intervals. The uniform tail bound
\[ G_n(a)\leq2a e^{-a^2/3} \]
correctly follows from the earlier bound and prevents maximizing points from escaping to infinity. Compact convergence plus this tail control therefore justifies convergence of the maxima.

The limiting-maximizer analysis is correct: the derivative of \(g\) is as stated, and the strict Gaussian-tail inequality supplies the claimed signs. The numerical values independently check as
\[ a_\star\approx0.7517915247, \qquad C\approx0.3399424150. \]
Finally, \(n/k\to1\) correctly transfers the asymptotic to \(k\).

4. Exact evaluation and output obstruction

The common-denominator construction uses \(O(L)\) denominator bits. The definitions of \(b_i\), \(B\), and \(S_i\) correctly produce the displayed rational evaluation formula.

The term recurrence performs exact integer divisions. Its denominator is nonzero because \(b_i\leq D/2\), so \(D-b_i>0\). Coordinates with \(b_i=0\) are also valid: their subsequent recurrence terms vanish.

The arithmetic-operation counts, intermediate bit-length bounds, schoolbook bit-time bound, and explicit rational-output bound are consistent. Initialization by exponentiation fits within the stated conservative bound.

The output-size obstruction is valid. For the selected powers-of-two values of \(r\), the binomial coefficient is odd, the recurrence gives \(S_n\equiv2\pmod4\), and the ratio numerator consequently has exactly two factors of \(2\). The reduced denominator is therefore \(2^{2n-2}\).

This establishes an \(\Omega(k)\) explicit-output requirement along an infinite family with input length \(O(\log k)\). It rules out polynomial time in binary input length alone for conventional explicit rational output. The prover appropriately identifies this as an output obstruction rather than a hardness reduction.

5. Certified approximation and witnesses

The large-\(n\) cutoff correctly guarantees both additive accuracy of the estimate \(1\) and \(\varepsilon\)-optimality of the balanced witness.

The \(n=1\) witness has positive dyadic masses and satisfies the required inequality with the stated bit size.

For the remaining branch, both derivative bounds and the resulting \(6n\)-Lipschitz estimate are valid, including the continuous extension at zero.

The bisection signs correctly locate the unique maximizer. An exact zero supplies a rational maximizer. Otherwise, the stated number of bisections and final-midpoint error bound imply the claimed ratio error. Downward dyadic rounding adds at most the specified grid spacing.

The intermediate bit sizes, total time bound, and substitution \(n<4/\varepsilon^2\) are consistent. The witness has exactly two positive dyadic masses, and its encoding uses \(O(1+\log(1/\varepsilon))\) bits.

The final additive-evaluation claim for a given society also follows from the uniform ratio bound and the exact-evaluation algorithm.

Required feedback

None. No additional clarification or missing mathematical argument is needed. Preserve the distinction between numerical-\(k\) exact complexity and binary-input approximation complexity when summarizing the result.

⟨structured verdict parsed — rendered above⟩