The Condorcet generating-function conjecture for the coefficients bk,b_{k,\ell}

Let bk,b_{k,\ell} be the doubly indexed sequence defined recursively from the coefficients ck,c_{k,\ell} by setting bk,=0b_{k,\ell}=0 when k<0k<0 or <0\ell<0, and, for k,0k,\ell\geq 0, using the auxiliary quantities

xk,=i,j0\i+jkbi,kijbj,(i+1)(i+j+2),yk,=i=0k(1)kibi,i+1,x_{k,\ell}=\sum_{\substack{i,j\geq 0\i+j\leq k}}\frac{b_{i,k-i-j}b_{j,\ell}}{(i+1)(i+j+2)},\qquad y_{k,\ell}=\sum_{i=0}^{k}(-1)^{k-i}\frac{b_{i,\ell}}{i+1},

with

ck,=(1)k+(k+k)(1)(k+k)+(1)k+(+1)k++2,c_{k,\ell}=(-1)^{k+\ell}\binom{k+\ell}{k}-\frac{(-1)^\ell\binom{k+\ell}{k}+(-1)^{k+\ell}(\ell+1)}{k+\ell+2},

and bk,=(k+1)(xk1,+yk1,ck+1,)b_{k,\ell}=(k+1)(x_{k-1,\ell}+y_{k-1,\ell}-c_{k+1,\ell}). Define

B(x,P)=k=0=0bk,xkP.B(x,P)=\sum_{k=0}^{\infty}\sum_{\ell=0}^{\infty}b_{k,\ell}x^kP^\ell.

The Condorcet generating-function conjecture. (i) The series B(x,P)B(x,P) converges for 0x<120\leq x<\frac12 and xP12x\leq P\leq\frac12; (ii) B(x,P)0B(x,P)\geq 0 on the same region; and (iii)

0PB(x,P)dx=1P+112P1+2P\int_0^P B(x,P)\,dx=\frac{1}{P+1}-\sqrt{\frac{1-2P}{1+2P}}

for 0P120\leq P\leq\frac12. The conjecture concerns analytic and positivity properties of the generating function arising in the analysis of Condorcet voting schemes; the accompanying comments report numerical evidence for convergence away from (12,12)(\frac12,\frac12) and suggest coefficient-based approaches to non-negativity, but do not resolve the three claims.

Sources & referencesView supporting material

Primary source

Flavio Chierichetti and Jon Kleinberg, “Voting with Limited Information and Many Alternatives”, arXiv:1110.1785 (2011).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.