# Existence of solutions of a polynomial system

Fix $k \in \mathbb{N}$, $k \geq 1$. Let $p \in [0,1]$ and $x = (x_0, \ldots, x_k)$ be a $(k+1)$-dimensional real vector, and define $$S(p,x) = -x_0^2 + \sum_{i=0}^k {k \choose i} p^i (1 - p)^{k - i} \cdot (x_i - p)^2.$$ Experiments show that for small values of $k$ $$\exists x \in \mathbb{R}^{k+1} \,.\, \forall p \in [0,1] \,.\, S(p,x) = 0.$$ In other words, there are $x_i$'s such that $S(x,p)$ is identically zero as a polynomial in $p$.

For a given $k$ we can expand $S(x,p)$ as a polynomial in $p$ and equate the coefficients to $0$. For $k = 2$ we get \begin{align*} 0&=0 \\ -x_0^2-2 x_0+x_1^2&=0 \\ 2 x_0-2 x_1+1&=0 \\ \end{align*} and this has two solutions: $$x = (\frac{1}{2} (-1-\sqrt{2}),\frac{1}{2},\frac{1}{2} (3+\sqrt{2}))$$ and $$x = (\frac{1}{2} (-1+\sqrt{2}),\frac{1}{2},\frac{1}{2} (3-\sqrt{2})).$$ For $k = 1, 2, 3, 4, 5, 6, 7$ there are $1, 2, 4, 8, 14, 28, 48$ solutions respectively, according to Mathematica. According to OEIS this is A068912, "the number of $n$ step walks (each step $\pm 1$ starting from $0$) which are never more than $3$ or less than $-3$." This is kind of interesting because the problem arises in statistics, see John Mount's blog post for background.

Question: Is there a solution for every $k$?

Addendum: John says he wants soltions in $[0,1]^{k+1}$...

Here is the relevant Mathematica code:

s[k_, p_, x_] := Sum[Binomial[k, i] * p^i* (1 - p)^(k - i)* (Subscript[x, i] - p)^2, {i, 0, k}]  Subscript[x, 0]^2
xs[k_] := Table[Subscript[x, i], {i, 0, k}]
system[k_, p_, x_] := Thread[CoefficientList[s[k, p, x], p] == 0]
solutions[k_] := Solve[system[k, p, x], xs[k], Reals]


To see the system of equations for $k = 4$, type

system[4, p, x] // ColumnForm


To see the solutions for $k = 4$, type

solutions[4]


To make a table of counts of solutions up to $k = 7$, type

Table[{k, Length@solutions[k]}, {k, 1, 7}] // ColumnForm

• In other words, we have a family of one-sheeted hyperboloids $$\sum_{i=1}^k {k \choose i} p^{i-1} (1 - p)^{k - i-1}(x_i-p)^2 - \frac{1}{1-p}(x_0-(p-1))^2 = 1$$ in $\mathbb{R}^{k+1}$ parametrised by $p \in [0,1]$ and we want to know whether there is a point lying in all of them at once. – Vít Tuček Aug 1 '14 at 13:09
• The polynomial $S(p,x)$ is actually divisible by $p$, which means that we have a well defined mapping $\mathbb{R}^{k+1} \to \mathbb{R}^{k+1}$. This allows us to use topological methods such as this one: en.wikipedia.org/wiki/… – Vít Tuček Aug 1 '14 at 13:32
• Did you try to express $S(p,x)$ in terms of Bernstein basis? Can Mathematica handle that at least for some small $k$? – Vít Tuček Aug 1 '14 at 13:40
• Always $x_k=1\pm x_0$, so for solutions in $[0,1]^{k+1}$ it must be that $x_k=1-x_0$. This can continue to $x_{k-1}$ and so on, but I don't know how to see that it remains real, let alone in $[0,1]$. – Brendan McKay Aug 2 '14 at 4:11

The solutions described via the link http://winvector.github.io/freq/explicitSolution.html (posted in one of the earlier answers) can be given by the following formula: $$x_i=\frac{(k-2i)\sqrt{k}+(2i-1)k}{2k(k-1)}=\frac{1}{2(1+\sqrt{k})}+\frac{i}{\sqrt{k}(1+\sqrt{k})}.$$ Note that (when $k$ is fixed):

• $x_i$ is an increasing function of $i$, and we have $$x_0=\frac{1}{2(1+\sqrt{k})}, \quad x_k=\frac{1+2\sqrt{k}}{2+2\sqrt{k}},$$
so all these numbers are between 0 and 1.

• Moreover, we have $x_i=a+bi$, so $S(p,x)$ can be represented as $$-x_0^2+\sum_{i=0}^k\binom{k}{i}p^i(1-p)^{k-i}(U+Vi+Wi^2),$$ where $U$, $V$ and $W$ depend on $k$ and $p$ but not on $i$. It remains to use formulas \begin{gather} \sum_{i=0}^k\binom{k}{i}p^i(1-p)^{k-i}=1,\\ \sum_{i=0}^k i\binom{k}{i}p^i(1-p)^{k-i}=kp,\\ \sum_{i=0}^k i(i-1)\binom{k}{i}p^i(1-p)^{k-i}=k(k-1)p^2 \end{gather} (which are obvious) to check directly that the formulas for $x_i$ as above give a solution.

This solution also simplifies to $x_i = (\frac{1}{2}\sqrt{k} + i)/(\sqrt{k}+k)$ which is exactly the smoothed estimate of the win-rate of a coin flipped $k$ times showing $i$ wins with $\sqrt{k}$ "pseudo-observations" (half wins, half losses) added first (or Bayesian inference starting with $\beta(\sqrt{k}/2,\sqrt{k}/2)$ priors, $\beta(1/2,1/2)$ being Jeffreys priors, and $\beta(1,1)$ being standard Laplace smoothing).

This is not a solution but some background to the question.

Define $$S(k,p,x) = \sum_{i=0}^k {k \choose i} p^i (1-p)^{k-i} (x_i-p)^2.$$ Define $$f(k) = \mathrm{argmin}_x \max_p S(k,p,x).$$ Then $f(k)$ is the minimax square-loss solution to trying to estimate the win rate of a random process by observing $k$ results (Wald wrote on this). The neat thing is: we can show if there is a real solution $x$ in the interior of $[0,1]^{k+1}$ to $S(k,p,x) = x_0^2$ then $x=f(k)$. Meaning we avoided two nasty quantifiers. See this file for some experimental examples. Also, a change of variables $z = p/(1-p)$ makes collecting terms easier.

• I hope my edits didn't spoil anything. Except, here $S$ does not have the $-x_0^2$ term, but that doesn't matter when we're just looking for extrema. – Andrej Bauer Aug 1 '14 at 17:37
• A note to user56665: instead of editing John Mount's answer to the question to give your observations, just submit them as a second answer. – Jeremy Rouse Aug 4 '14 at 20:16
• (I may well be mistaken, but the wording of the edits makes me think that 56665 is John Mount.) – Emil Jeřábek Aug 4 '14 at 20:40

Having trouble formatting. Here is a [line of attack][1] . Also a [proof of the problem mapping][2]. Apparently I am both user 56-something and "John Mount" but have lost control of at least one of those accounts.

• You should try using it through not-iPhone. – Andrej Bauer Aug 5 '14 at 8:21
• Yeah, sorry about the iPhone bits. It seems to have created an account I can't get control of that posted the other answer. Vladimir Dotsenko's observation that the $x_i$ are evenly spaced was really awesome though. Much simpler than I expected. – John Mount Aug 5 '14 at 21:56
• John, I have put in a request to merge the other account (unregistered) into the one used to post this answer (registered). – Todd Trimble Aug 5 '14 at 23:56
• @JohnMount: and now that you're on Mathoverflow, make sure statistics and probability are your favorite tags, and help answer some questions! – Andrej Bauer Aug 6 '14 at 9:14