4
$\begingroup$

Given a set of points in the plane with distinct $x$-coordinates, each point colored black or white. A polynomial $P(x)$ "divides" the set of points if no black point lies above $P(x)$ and no white point lies below $P(x)$, or vice versa. Points of any color can lie on $P(x)$.

What is the least $k$ such that any valid set of $n$ points can be divided by a polynomial of degree at most $k$? We can do $k=n-2$ by having a polynomial pass through any $n-1$ points, thus trivially satisfying the condition of dividing the points.

$\endgroup$
7
  • 1
    $\begingroup$ This obviously depends on how those two sets of points are distributed. But as you already said $k=n-2$ is the lower bound for a general case. $\endgroup$
    – flawr
    Commented Feb 1, 2016 at 21:02
  • $\begingroup$ Can you prove that? $\endgroup$ Commented Feb 1, 2016 at 21:03
  • 1
    $\begingroup$ I think what we need to prove here is that for all $n \in \Bbb{N}$, there exists a set of $n$ black or white points such that any polynomial of degree less than $k(n)$ does not divide the set of points. If our answer is $k(n)=n-2$, then we must prove that any polynomial of degree less than $n-2$ can not divide some set of $n$ points. $\endgroup$ Commented Feb 1, 2016 at 21:13
  • 1
    $\begingroup$ A start: You need $k=n-2$ for $n=3,4$. For $n=3$ take the white points $(0,0),(2,2)$ and the black point $(1,1)$. No constant can divide them. For $n=4$ take a square (rotated off vertcal/horizontal) with diagonally opposite points the same color. No line can divide them. Similarly, an equilateral triangle of white points and central black point needs $k=2$. I think for $n=5$ you can force $k=3$ with a square of white points and the center a black point. It seems a regular $n-1$gon of white points and a central black point is a challenging configuration for $k=-3$ but I have no proof. $\endgroup$ Commented Feb 1, 2016 at 21:35
  • $\begingroup$ As a side note, if the condition is stregthened so that no points are allowed to lie on $P(x)$ then it trivially follows that $k \ge n - 1$ by choosing points of alternating colors on a horizontal line (which would require $P$ to have $n - 2$ local extrema, thus degree $\ge n - 1$). $\endgroup$
    – dxiv
    Commented Feb 1, 2016 at 22:38

1 Answer 1

3
$\begingroup$

For all $n$, there is a way to choose the points & colors that forces $ P $ to have degree at least $ n-2 $ .

Assume $ n \geq 3 $ (the smaller cases are easy).

Choose the points $ \{(i,0) | 1 \leq i \leq n-2\} \cup \{(n-1,1),(n,n^2)\}$. Color them alternating white and black in order of their $ x $-coordinates.

For any $ 1 \leq i \leq n-3 $, we have that either $ P(i) \geq 0$ and $ P(i+1) \leq 0 $ or vice versa. Since $ P $ is non-zero somewhere between $ i $ and $ i + 1 $ ($ P $ can't be the $ 0 $ polynomial - that doesn't divide the points), $ P $ has a root somewhere in $ [i,i+1]$. It is possible for two of these roots to be the same, but it's not hard to see that this must either be double root, or there will be additional roots in one of the two intervals. This gives a root of $P$ for each $ i $, totaling $ n - 3 $ roots.

Assume that $ P $ has degree $ k = n-3 $. Then $ P $ can't have more roots than we've already found. Let $ x_1, x_2 ... x_{n-3} $ be these roots.

Since the two last points are both above the $x$-axis, and one of those points is a lower bound, $ P $ must stay above the $x$-axis after its last root.

Now we consider the two cases, when the final point is a lower bound or an upper bound.

Case 1: The final point is an upper bound.

The point at $(n-2,0)$ is also an upper bound. $ P $ is, after its last root, on the "wrong" side of the $x$-axis for this point. Its last root is at most $ n-2 $, so it must pass through the point $(n-2,0)$.

Then it will be on the wrong side of the $x$-axis for the previous point, and the previous root is at most $ n-3 $, so $ P $ must pass through the point $(n-3,0)$.

This continues through all the points, and $ P $ must pass through the 2nd point, only to be on the wrong side of the $x$-axis for the first point. But then $ P $ already has $n-3$ roots, so it can't cross the $x$-axis again to get to the correct side for the 1st point. Thus, we have a contradiction.

Case 2: The final point is a lower bound.

Since we know all the roots of $ P $, we can write it as $ P(x) = a \displaystyle\prod_{i=1}^{n-3} (x-x_i)$.

Now, we can give an upper bound for $ \dfrac{P(n)}{P(n-1)}\\ = \dfrac{\displaystyle\prod_{i=1}^{n-3} (n-x_i)}{\displaystyle\prod_{i=1}^{n-3} (n-1-x_i)} \\ \leq \dfrac{\displaystyle\prod_{i=1}^{n-3} (n-i)}{\displaystyle\prod_{i=1}^{n-3} (n-1-(i+1))} \\ = \dfrac{\displaystyle\prod_{i=1}^{n-3} (n-i)}{\displaystyle\prod_{i=1}^{n-3} (n-2-i)} \\ = \dfrac{\displaystyle\prod_{i=3}^{n-1} i}{\displaystyle\prod_{i=1}^{n-3}i}\\ = \dfrac{(n-1)!/2}{(n-3)!}\\ = \dfrac{(n-1)(n-2)}{2}\\ < n^2 $

But since the last point, $(n,n^2)$ is a lower bound, and the 2nd last point, $(n-1, 1)$ is an upper bound, we have $ P(n) \geq n^2 $ and $ P(n-1) \leq 1 $, so $ \dfrac{P(n)}{P(n-1)} \geq n^2 $, and we've reached a contradiction.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .