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

About 15 years old · traced to

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,j≥0\i+j≤kbi,k−i−jbj,ℓ(i+1)(i+j+2),yk,ℓ=∑i=0k(−1)k−ibi,ℓ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)(xk−1,ℓ+yk−1,ℓ−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∞∑ℓ=0∞bk,ℓ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 0≤x<120\leq x<\frac12 and x≤P≤12x\leq P\leq\frac12; (ii) B(x,P)≥0B(x,P)\geq 0 on the same region; and (iii)

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

for 0≤P≤120\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.

References

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.