Answer: \(b(m,\tau,L)=\lfloor\log_2 N_{m,\tau,L}\rfloor\), where \(N_{m,\tau,L}\) is given by the explicit finite coefficient formula in Section 3. Uniformly computable compiler and decoder maps attain this exact length.
Theorem 2 (Borda) — class: other
Fix \(m,\tau,L\). Each region has total mass \(1/2\) over at most \(\tau\) ranking types, with each type mass a binary rational of reduced numerator and denominator bit length at most \(L\). What is the minimum worst-case number \(b\) of bits for a compiler \(\sigma\) such that \(\sigma(\mu)=\sigma(\mu')\) implies that, for every allowed complementary distribution \(\nu\), the Borda winners of \(\mu+\nu\) and \(\mu'+\nu\) agree under the paper’s fixed tie-breaking order? Give a compiler and decoder attaining the minimum, or tight bounds on \(b\), with the maps computable from the rational input.
Fix integers \(m\ge2\), \(\tau\ge1\), and \(L\ge2\), and candidates \(c_1,\ldots,c_m\), with ties resolved in that order.
A society is given by its support: the list of ranking types with positive mass, each mass a binary rational. Types are strict complete rankings; support size counts listed types, not the \(m!\) possible rankings.
Let \(\mathcal D_{m,\tau,L}\) contain all such societies of total mass \(1/2\), support size at most \(\tau\), and reduced mass numerators and denominators each of bit length at most \(L\). Both the known region \(\mu\) and every allowed complement \(\nu\) belong to this domain.
Let \(w(\mu+\nu)\) be the unique Borda winner, using mass-weighted scores and the fixed tie order.
A compiler \(\sigma:\mathcal D_{m,\tau,L}\to\{0,1\}^{*}\) is valid if \(\sigma(\mu)=\sigma(\mu')\) implies \(w(\mu+\nu)=w(\mu'+\nu)\) for every allowed \(\nu\). Its decoder receives the summary and the full support of \(\nu\), together with \(m,\tau,L\), and returns that winner.
Strings may have different lengths, including zero; their boundaries are supplied, and no prefix condition is imposed. Define \(b(m,\tau,L)=\min_{\sigma}\max_{\mu\in\mathcal D_{m,\tau,L}}|\sigma(\mu)|\), minimizing over valid compilers with uniformly computable compiler and decoder maps. State running times in \(m,\tau,L\) and the actual support sizes.
What is the minimum worst-case summary length \(b(m,\tau,L)\), exactly or up to asymptotically tight bounds, achievable by computable compiler and decoder maps?
For discrete regions of \(k\ge1\) known and \(u\ge1\) complementary votes, Borda compilation requires \(\Theta(m\log(m\min\{k,u\}))\) bits; the corresponding upper-bound compilers run in polynomial time. [Xia and Conitzer](https://ojs.aaai.org/index.php/AAAI/article/download/7627/7488).
No result settling this exact bounded-support, bounded-rational-mass question was located in the literature search.
I interpret “binary rational” as a rational number represented by its binary numerator and denominator.
An exact answer is available through an explicit finite coefficient formula. The key structural fact is that two known regions are indistinguishable precisely when their Borda score vectors agree. Consequently, optimal summaries can be constructed by enumerating distinct attainable score vectors.
The resulting optimal compiler is uniformly computable, although its running time can be large. Polynomial-time compilers with explicit length bounds are given below.
For a ranking \(\pi\), let \(r_j(\pi)\in\{0,\ldots,m-1\}\) be the Borda score assigned to \(c_j\). Define
\(s_j(\mu)=\sum_{\pi\in\operatorname{supp}(\mu)}\mu(\pi)r_j(\pi)\), and \(s(\mu)=(s_1(\mu),\ldots,s_m(\mu))\).
Every region has mass \(1/2\), so
\(\displaystyle \sum_{j=1}^{m}s_j(\mu)=\frac{m(m-1)}4.\)
Let \(R\mu\) be obtained by reversing every ranking in \(\mu\), preserving its mass. Reversal preserves distinctness of ranking types, support size, and all numerator and denominator bounds. Thus \(R\mu\) is an allowed complement. Moreover,
\(\displaystyle s_j(R\mu)=\frac{m-1}{2}-s_j(\mu).\)
Lemma. For \(\mu,\mu'\in\mathcal D_{m,\tau,L}\),
\(\displaystyle \bigl[w(\mu+\nu)=w(\mu'+\nu)\text{ for every }\nu\in\mathcal D_{m,\tau,L}\bigr]\quad\Longleftrightarrow\quad s(\mu)=s(\mu').\)
Proof. Equality of score vectors immediately implies equality of winners against every complement.
Conversely, assume equality of winners against every allowed complement, and put \(\delta_j=s_j(\mu')-s_j(\mu)\).
Against \(R\mu\), every candidate in \(\mu+R\mu\) has score \((m-1)/2\); hence its winner is \(c_1\). The scores in \(\mu'+R\mu\) are \((m-1)/2+\delta_j\). Its winner must also be \(c_1\), implying
\(\delta_1\ge\delta_j\quad\text{for every }j.\)
Against \(R\mu'\), the winner of \(\mu'+R\mu'\) is \(c_1\), while the scores in \(\mu+R\mu'\) are \((m-1)/2-\delta_j\). Therefore
\(\delta_1\le\delta_j\quad\text{for every }j.\)
Thus all \(\delta_j\) are equal. Their sum is zero because the two regions have the same total Borda score. Hence every \(\delta_j=0\). \(\square\)
Let
\(\displaystyle N_{m,\tau,L}=\left|\{s(\mu):\mu\in\mathcal D_{m,\tau,L}\}\right|.\)
The lemma shows that every valid compiler must use at least this many distinct strings.
There are exactly
\(\displaystyle \sum_{\ell=0}^{b}2^\ell=2^{b+1}-1\)
binary strings of length at most \(b\). Consequently, distinguishing \(N_{m,\tau,L}\) score vectors requires
\(\displaystyle b\ge\left\lfloor\log_2N_{m,\tau,L}\right\rfloor.\)
This bound is achievable. Sort the distinct attainable score vectors lexicographically, with indices \(i\in\{0,\ldots,N_{m,\tau,L}-1\}\). Encode index \(i\) by writing \(i+1\) in binary and deleting its initial \(1\). In particular, index zero receives the empty string. The maximum length is \(\lfloor\log_2N_{m,\tau,L}\rfloor\).
The decoder prepends \(1\), recovers the index, reconstructs its score vector, adds the complement’s score vector, and applies the fixed tie order.
Thus
\(\boxed{\displaystyle b(m,\tau,L)=\left\lfloor\log_2N_{m,\tau,L}\right\rfloor.}\)
The next section gives an explicit coefficient formula for \(N_{m,\tau,L}\), involving only the parameters and finite polynomial operations.
Put
\(\displaystyle Q=2^L-1,\qquad D=\operatorname{lcm}(1,2,\ldots,Q).\)
The possible individual masses are exactly
\(\displaystyle W_L=\left\{\frac pq:2\le q\le Q,\ 1\le p\le\lfloor q/2\rfloor,\ \gcd(p,q)=1\right\}.\)
Indeed, every mass is at most \(1/2\), so the denominator bound already ensures the numerator bound. Define the integer set
\(\displaystyle E_L=\{Da:a\in W_L\}.\)
Every listed mass is at least \(1/Q\). Therefore a region with \(t\) types satisfies \(t/Q\le1/2\), giving the effective support bound
\(\displaystyle T=\min\left\{\tau,m!,\left\lfloor Q/2\right\rfloor\right\}.\)
This maximum is attainable: choose \(T\) distinct rankings, each with mass \(1/(2T)\). Its reduced denominator satisfies \(2T\le Q\).
For indeterminates \(z,x,y_1,\ldots,y_{m-1}\), form
\(\displaystyle G(z,x,\mathbf y)=\prod_{\pi\in S_m}\left(1+z\sum_{a\in E_L}x^a\prod_{j=1}^{m-1}y_j^{a r_j(\pi)}\right).\)
Here \(S_m\) denotes the set of strict rankings. Let
\(\displaystyle H_{m,\tau,L}(\mathbf y)=\sum_{t=1}^{T}[z^t x^{D/2}]\,G(z,x,\mathbf y).\)
The notation in brackets means coefficient extraction in the displayed variables. Since \(D\) is even, \(D/2\) is an integer. Set \(M=D(m-1)/2\). Then the requested exact answer is
\(\displaystyle \boxed{\ b(m,\tau,L)=\left\lfloor\log_2\left(\sum_{\mathbf e\in\{0,\ldots,M\}^{m-1}}\mathbf 1\!\left\{[\mathbf y^{\mathbf e}]H_{m,\tau,L}>0\right\}\right)\right\rfloor.\ }\)
Proof of the counting formula. In the factor indexed by \(\pi\), choosing \(1\) omits that ranking; choosing another term assigns it one permitted positive mass. Thus a product term chooses a support of distinct rankings and one mass per type.
The exponent of \(z\) counts the support size. The exponent of \(x\) is \(D\) times total mass. Extracting \(z^t x^{D/2}\), for \(1\le t\le T\), therefore selects exactly the allowed regions.
For a selected region, the exponent of \(y_j\) is \(Ds_j(\mu)\). All coefficients are nonnegative integers, so a coefficient is positive precisely when its score vector is attained.
Finally, the first \(m-1\) scores determine the last score through their fixed sum \(m(m-1)/4\). Counting the positive coefficients therefore counts distinct complete score vectors, without counting different representations of the same vector separately. This proves the formula. \(\square\)
The coefficient formula can be evaluated by enumeration without constructing a polynomial with enormous exponents.
Write \(n=m!\), \(R=|W_L|\), and
\(\displaystyle A=\sum_{t=1}^{T}\binom nt R^t.\)
There are at most \(A\) candidate supports with assigned masses before checking total mass. Enumerate them, discard those whose masses do not sum to \(1/2\), compute their score vectors, sort, and remove duplicates. This produces the dictionary used by the optimal compiler and decoder.
For an explicit conservative bit-complexity bound, define
\(\displaystyle C=T\bigl(m\lceil\log_2m\rceil+2L\bigr)+\lceil\log_2(T+1)\rceil+3,\)
and
\(\displaystyle F=Q^2L^3+A C^4.\)
Both maps can reconstruct the dictionary in \(O(F)\) bit operations, using elementary integer arithmetic. To justify this bound:
Here \(m\), \(T\), and \(\log(A+1)\) are all \(O(C)\), so these costs are covered by \(O(F)\).
If the actual known and complementary support sizes are \(t\) and \(u\), respectively, conservative total bounds are:
\(\displaystyle \text{compiler: }O\!\left(F+mt\bigl(tL+\log_2(m(t+1))\bigr)^2\right),\)
\(\displaystyle \text{decoder: }O\!\left(F+m(u+1)\bigl((T+u)L+\log_2(m(T+u+1))\bigr)^2\right).\)
The additional terms cover computing the input scores and exact winner comparisons. These are uniform algorithms: their finite loops and arithmetic operations are determined by \(m,\tau,L\).
A simpler description of the enumeration cost is
\(\displaystyle 2^{\,O(T(m\log m+L))}\operatorname{poly}(m,T,L).\)
Thus the exact optimum is achievable by computable maps; this construction does not establish polynomial-time optimal compilation.
Let
\(\displaystyle h=\lceil\log_2(T+1)\rceil,\qquad r=\lceil\log_2(m!)\rceil,\qquad \ell=\lceil\log_2m\rceil.\)
For a known region with actual support size \(t\), two straightforward encodings are available.
Encode the support. Store \(t\) in \(h\) bits. For each type, store its permutation index in \(r\) bits and its reduced numerator and denominator in \(L\) bits each. The length is
\(\displaystyle h+t(r+2L).\)
Encode exact scores. Let \(d\) be the product of the \(t\) reduced denominators. Then \(d<2^{tL}\), and \(a_j=ds_j(\mu)\) is an integer satisfying \(0\le a_j\le d(m-1)/2\).
Store \(t\), then \(d\) in \(tL\) bits, and the first \(m-1\) integers \(a_j\), each in \(tL+\ell\) bits. The last numerator is recovered as
\(\displaystyle a_m=\frac{dm(m-1)}4-\sum_{j=1}^{m-1}a_j.\)
The length is
\(\displaystyle h+mtL+(m-1)\ell.\)
Using one mode bit and selecting the shorter encoding gives the actual length bound
\(\displaystyle 1+h+\min\{t(r+2L),\,mtL+(m-1)\ell\}.\)
Consequently,
\(\displaystyle \boxed{\ b(m,\tau,L)\le1+h+\min\{T(r+2L),\,mTL+(m-1)\ell\}.\ }\)
Both encodings and their decoders run in polynomial time. With ordinary permutation indexing and schoolbook integer arithmetic, conservative bounds are
\(\displaystyle \text{compiler: }O\!\left(tm^4(\log_2m)^2+mt\bigl(tL+\log_2(m(t+1))\bigr)^2\right),\)
\(\displaystyle \text{decoder: }O\!\left(tm^4(\log_2m)^2+m(t+u)\bigl((t+u)L+\log_2(m(t+u+1))\bigr)^2\right).\)
In the score mode, the permutation-processing term is unnecessary.
If \(\tau=1\), the sole mass must be \(1/2\). Every ranking yields a distinct score vector. Therefore
\(\boxed{\displaystyle b(m,1,L)=\lfloor\log_2(m!)\rfloor.}\)
If \(L=2\), then \(Q=3\) and \(T=1\), regardless of \(\tau\). Hence
\(\boxed{\displaystyle b(m,\tau,2)=\lfloor\log_2(m!)\rfloor.}\)
For all parameters, the pure-ranking regions give
\(\displaystyle b(m,\tau,L)\ge\lfloor\log_2(m!)\rfloor=\Omega(m\log m).\)
Suppose \(\tau\ge2\) and \(L\ge3\). Fix two distinct rankings, and let \(q=2^{L-1}\). For every odd \(p\) with \(1\le p<q/2\), assign the two masses
\(\displaystyle \frac pq,\qquad \frac12-\frac pq=\frac{q/2-p}{q}.\)
Both reduced denominators are at most \(q\le Q\), and both numerators satisfy the bound. There are \(2^{L-3}\) such choices. Their score vectors are distinct because the difference between the two ranking score vectors is nonzero. Including the two endpoint regions gives
\(\displaystyle N_{m,\tau,L}\ge2+2^{L-3}.\)
Combining this with the pure-ranking bound yields, for \(\tau\ge2\),
\(\displaystyle b(m,\tau,L)=\Omega(m\log m+L).\)
For \(\tau=2\), support serialization gives the matching upper bound. Thus, uniformly in \(m,L\),
\(\boxed{\displaystyle b(m,2,L)=\Theta(m\log m+L).}\)
For \(m=2\) and \(\tau\ge2\), a region is determined by a mass \(a\in[0,1/2]\) on the ranking placing \(c_1\) first.
For an interior mass \(a=p/q\) in lowest terms, its complementary mass is \((q-2p)/(2q)\). If \(q\) is odd, this fraction has reduced denominator \(2q\), so it is allowed exactly when \(q\le\lfloor Q/2\rfloor\). If \(q\) is even, its reduced denominator is either \(q\) or \(q/2\), so it is always allowed when \(q\le Q\).
For each \(q>2\), precisely \(\varphi(q)/2\) reduced fractions have \(0<p/q<1/2\). Therefore
\(\displaystyle N_{2,\tau,L}=2+\frac12\left(\sum_{\substack{4\le q\le Q\\q\text{ even}}}\varphi(q)+\sum_{\substack{3\le q\le\lfloor Q/2\rfloor\\q\text{ odd}}}\varphi(q)\right),\)
and
\(\boxed{\displaystyle b(2,\tau,L)=\lfloor\log_2N_{2,\tau,L}\rfloor.}\)
For example, \(L=3\) gives \(N_{2,\tau,3}=5\) and \(b(2,\tau,3)=2\). The preceding lower bound and the \(O(Q^2)\) count of possible fractions also show \(b(2,\tau,L)=\Theta(L)\).
The supplied discrete theorem gives an additional lower bound. Take \(T\) known votes and \(T\) complementary votes, and scale each vote to mass \(1/(2T)\). After merging repeated types, every mass has reduced numerator at most \(T\) and denominator at most \(2T\le Q\); each support has at most \(T\le\tau\) types. Scaling preserves the Borda winner, including the fixed tie order. Therefore the discrete lower bound applies:
\(\displaystyle b(m,\tau,L)=\Omega\bigl(m\log(mT)\bigr).\)
The required discrete result, with the same fixed-order tie convention, is [Xia and Conitzer, Theorem 2](https://ojs.aaai.org/index.php/AAAI/article/download/7627/7488).
These bounds do not assert one elementary asymptotic formula uniformly over all three parameters. The coefficient formula above nevertheless determines the minimum exactly for every parameter triple, with uniformly computable maps attaining it.
⟨structured verdict parsed — rendered above⟩
The prover resolves the requested minimum summary length exactly, under its explicitly stated interpretation of “binary rational.” The score-vector lemma, coefficient formula, and optimal encoding are correct. The additional running-time bounds and special cases are consistent with that result. I found no major or minor mathematical issues.
1. Domain interpretation and admissible masses
The prover interprets masses as arbitrary rational numbers whose reduced numerator and denominator are represented in binary. This is consistent with the task’s explicit bounds on both quantities. The interpretation is stated, so it is not an unstated assumption.
With \(Q=2^L-1\), the set \(W_L\) correctly describes all possible individual masses:
The domain is nonempty for every permitted parameter triple: a single ranking with mass \(1/2\) satisfies all bounds.
2. Indistinguishability lemma
Every ranking assigns the scores \(0,\ldots,m-1\) once each. Consequently, the stated total score \(m(m-1)/4\) is correct for a region of mass \(1/2\).
Reversal is a bijection on ranking types. It preserves support size, distinctness, total mass, and reduced mass representations. Therefore both \(R\mu\) and \(R\mu'\) are allowed complements.
The identity
\(s_j(R\mu)=(m-1)/2-s_j(\mu)\)
is correct because reversal replaces each ranking score by its difference from \(m-1\).
The converse implication checks out step by step:
The fixed tie order is used correctly. Weak inequalities suffice because \(c_1\) has priority over every other candidate.
Thus equality of attainable score vectors is exactly the required equivalence relation.
3. Exact number of summary bits
The lemma establishes that distinct score vectors must receive distinct strings. Conversely, communicating the score vector suffices.
The count \(2^{b+1}-1\) correctly includes every string of length at most \(b\), including the empty string. For every positive integer \(N\), the least permissible maximum length is \(\lfloor\log_2N\rfloor\).
The proposed index encoding is injective: prepending \(1\) reverses the deletion operation, including for the empty string. Its maximum length is exactly the claimed value.
There is no hidden prefix requirement. The task explicitly supplies string boundaries, so this encoding is admissible.
4. Finite coefficient formula
The effective support bound
\(T=\min\{\tau,m!,\lfloor Q/2\rfloor\}\)
is correct. Every permitted positive mass is at least \(1/Q\), and there are only \(m!\) distinct ranking types.
The claimed attainability of this support bound is also correct: assigning mass \(1/(2T)\) to each of \(T\) distinct rankings respects the denominator bound and gives total mass \(1/2\).
The coefficient construction has the required properties:
Consequently, extracting the specified coefficients selects exactly the allowed societies. Nonnegative coefficients prevent cancellation.
Each coordinate exponent lies between \(0\) and \(M=D(m-1)/2\). The omitted final score is determined by the fixed total score, so projecting to the first \(m-1\) coordinates loses no distinction.
This is an explicit finite formula in the parameters, rather than merely a definition in terms of unknown equivalence classes. It satisfies the task’s allowance for an exact answer.
5. Uniform computability and enumeration bounds
The quantity
\(A=\sum_{t=1}^{T}\binom{m!}{t}R^t\)
correctly counts all choices of distinct support types and assigned permitted masses before imposing total mass.
Filtering, exact scoring, sorting, and removing duplicates therefore constructs the dictionary required by both optimal maps. The algorithms are uniform in the parameters.
The proposed conservative bit bounds are consistent:
The stated relations \(m,T,\log(A+1)=O(C)\) hold. In particular, the number of support assignments has logarithm bounded by a constant multiple of \(T(m\log m+L)\). Thus \(O(F)\) covers the listed dictionary operations.
The additional compiler and decoder terms account for the actual input support sizes and exact rational comparisons. The decoder’s use of \(T\) accommodates dictionary entries whose support is larger than the supplied complement’s support.
The simpler exponential bound is also consistent with these estimates. The prover correctly limits its conclusion: these optimal maps are computable, but their construction does not establish polynomial-time optimal compilation.
6. Polynomial-time upper-bound encodings
The support encoding has sufficient fields for the support size, permutation indices, and reduced masses.
For the score encoding:
The mode bit and support-size field make the formats decodable. Taking the shorter format yields the stated actual and worst-case length bounds.
Permutation processing and exact arithmetic fit the conservative polynomial running times. These encodings establish polynomial-time upper-bound compilers, without claiming that they attain the exact optimum.
7. Special cases and lower bounds
The special cases are correct:
For the two-ranking construction, \(q=2^{L-1}\) has an admissible denominator. For the stated odd numerators, both masses are positive and admissible, and there are exactly \(2^{L-3}\) choices. The resulting score vectors are distinct because the two fixed ranking vectors differ. The two endpoints are distinct from all interior choices.
Combining this construction with the factorial lower bound supports the stated \(\Omega(m\log m+L)\) bound. At \(L=2\), the already verified pure-ranking case covers the constant contribution from \(L\). Support serialization supplies the matching upper bound for \(\tau=2\).
For two candidates, the denominator analysis is correct. An odd reduced denominator becomes \(2q\) for the complementary mass; an even denominator becomes either \(q\) or \(q/2\). The totient count correctly excludes the endpoints and counts each interior mass once. The numerical example \(N_{2,\tau,3}=5\) and its resulting bit count are correct.
8. Transfer of the discrete theorem
The cited theorem states the required discrete Borda bound, and the paper explicitly uses the same fixed candidate-order tie convention. Its compilation definition also permits finite binary strings. These hypotheses match the application. [Xia and Conitzer, Theorem 2 and preliminaries](https://ojs.aaai.org/index.php/AAAI/article/download/7627/7488).
Scaling each of \(T\) votes to mass \(1/(2T)\), then merging repeated rankings, produces allowed regions: each reduced numerator is at most \(T\), each reduced denominator is at most \(2T\le Q\), and support size is at most \(T\le\tau\). Scaling preserves scores up to a common positive factor and hence preserves winners and ties.
Restriction of a valid continuous compiler to these embedded discrete profiles justifies the transferred lower bound.
Required feedback
No repair or additional mathematical clarification is required. The exact length result is established. The computational conclusion remains exactly as qualified by the prover: computable optimal maps and polynomial-time upper-bound maps, without a polynomial-time algorithm for optimal compilation or a hardness classification.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.