MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

3 Make the bounds tight. (You can interpolate $n$ points by a degree $n-1$ polynomial.)

To give an explicit answer, choose a system of coordinates $x,y$ such that no two points have the same $x$ coordinate. This is possible since the slopes of lines that pass through pairs of points in the set are only finitely many of all the slopes. Then use basic algebra or the Chinese remainder theorem to find a polynomial equation $y=f(x)$ that passes through all your points. $y-f(x)$ is irreducible so you're done.

(Proof: its degree in $\mathbb R[x][y]$ is one so it must be the product of a linear and a constant term, but no nontrivial constant terms divide it.)

Edit: A secondary question might be: what is the worst-case scenario lowest-degree polynomial that accomplishes this goal? This method shows that, with $n$ points, there is always a degree-$n$ degree $n-1$ irreducible polynomial. Sometimes, there is no degree $n-2$ polynomial: Take $n-1$ points on a line, and one off it. Then an irreducible polynomial vanishing at all $n$ points cannot vanish identically on the line, but vanishes at $n-1$ points on it, so has degree at least $n-1$.

2 added 477 characters in body

To give an explicit answer, choose a system of coordinates $x,y$ such that no two points have the same $x$ coordinate. This is possible since the slopes of lines that pass through pairs of points in the set are only finitely many of all the slopes. Then use basic algebra or the Chinese remainder theorem to find a polynomial equation $y=f(x)$ that passes through all your points. $y-f(x)$ is irreducible so you're done.

(Proof: its degree in $\mathbb R[x][y]$ is one so it must be the product of a linear and a constant term, but no nontrivial constant terms divide it.)

Edit: A secondary question might be: what is the worst-case scenario lowest-degree polynomial that accomplishes this goal? This method shows that, with $n$ points, there is always a degree-$n$ irreducible polynomial. Sometimes, there is no degree $n-2$ polynomial: Take $n-1$ points on a line, and one off it. Then an irreducible polynomial vanishing at all $n$ points cannot vanish identically on the line, but vanishes at $n-1$ points on it, so has degree at least $n-1$.

1

To give an explicit answer, choose a system of coordinates $x,y$ such that no two points have the same $x$ coordinate. This is possible since the slopes of lines that pass through pairs of points in the set are only finitely many of all the slopes. Then use basic algebra or the Chinese remainder theorem to find a polynomial equation $y=f(x)$ that passes through all your points. $y-f(x)$ is irreducible so you're done.

(Proof: its degree in $\mathbb R[x][y]$ is one so it must be the product of a linear and a constant term, but no nontrivial constant terms divide it.)