Is there some set of 2-d points so that there does not exist a function that connects them?

Let's say I have a set of points $\{(x_0,y_0),\ldots,(x_n,y_n)\}$. Does there exist some function $f$ so that $f(x_i) = y_i$? If so, how can I prove that for any arbitrary set of points there exists some function to connect it? Furthermore, how do I find this function?

(By a function, I really mean something along the lines of an equation, akin to that of $y=\text{blah blah blah } x \text{ blah}$ [a function of y].)

My current proof lays like this: Suppose that there is some function $f^\prime$ so that $mf^\prime(x_j-a)+b=y_j$; then, by transposition, we can set our function $f$ as such: $$f=\frac{f^\prime(x+a)-b}{k}.$$

I guess it boils down to the fact that if this function $f$ has some parent function $p[f]$, then all that needs to be done is modify $p(f)$ so that it becomes $f$.

Application: is there a function that passes through all of the points in the following set? $$\{(0,100),(1,0),(2,30),(3,-340),(4,1034.5)\}$$

My guess is that it would be harder to prove/impossible to prove if $\exists x_i\exists y_i\neg\exists(p,q)\in\mathbb{Z}^2\left[x_i=\frac pq\vee y_i=\frac pq\right]$ (i.e. if $x_i$ or $y_i$ is irrational).

Any help is appreciated!

• i think the problem needs more constraints. Simply define a function to take the values as prescribed for r$x_i$ and zero elsewhere. Done. – Mark Joshi Jun 11 '15 at 21:08

I think you meant to assume that each of the $x_i$'s are distinct, because otherwise there is clearly no function that will work. I also think that you want to find a continuous function.

With that assumption, there are many functions $f$ such that $f(x_i)=y_i$. The simplest way to construct such a function is to order the points so that $x_0 < x_1 < \dots < x_n$, construct a linear function $f_i$ defined on $[x_{i-1},x_i]$ with $f_i(x_{i-1})=y_{i-1}$ and $f_i(x_i)=y_i$, and then define the function $f$ to be piecewise linear, with $f(x) = f_i(x)$ if $x\in[x_{i-1},x_i]$. The $f_i$ functions don't need to be linear; it's just easy to write down what they are in that case, something like $$f_i(x) = \frac{y_i-y_{i-1}}{x_i-x_{i-1}}(x-x_{i-1}) + y_{i-1}.$$

If you want $f$ to be a polynomial, you should check out Lagrange interpolation.

I see at the end of your question that you asked about what might happen if the set of points $(x_i,y_i)$ is (countably) infinite. In that case, all bets are off -- every method of interpolation between points relies crucially on the assumption that there are finitely many points to interpolate between, and indeed, there are sets of points with no continuous interpolant, such as $$\{(r,0)\,:\,r\in\mathbb Q \land r<\sqrt 2\}\cup\{(r,1)\,:\,r\in\mathbb Q \land r>\sqrt 2\}.$$

Per the OP's request, some information about Lagrange interpolation.

Lagrange Interpolation

What we would like to do is find a polynomial $f$ such that $f(x_i)=y_i$. Here's the brilliant idea behind Lagrange interpolation: let's solve the easier problem of finding, for each $i$, a polynomial $f_i$ such that $$f_i(x_j) = \begin{cases} 1 &\text{if i=j} \\ 0 &\text{if i\neq j}. \end{cases}$$ Suppose for the moment that we have solved this simple problem. We can now construct the polynomial $f$ as the following weighted sum: $$f(x) = \sum_{i=0}^n y_i f_i(x).$$ Why does this work, and assuming it does, how can we find $f_i$?

If we plug in $x_j$ into $f(x)$, every term except the $j$th one will be zero because that was how we defined $f_i(x_j)$. And the $j$th term is $y_jf_j(x_j) = y_j\cdot 1 = y_j$. So $f(x_j)=y_j$, which is what we wanted.

Next, how can we find $f_i$? Saying that $f_i(x_j)=0$ for $i\neq j$ means that each $x_j$ with $i\neq j$ is a root of $f_i(x)$. So a good guess for $f_i$ would be something like $$f_i(x) = A\cdot(x-x_0)(x-x_1)\dots(x-x_{i-1})(x-x_{i+1})\dots(x-x_n) = A\cdot\prod_{j\neq i}(x-x_j),$$ where $A$ is a constant that we're free to choose. (The product notation means that for every $j$ such that $j\neq i$ [between $0$ and $n$, of course] we take a factor $x-x_j$, and then multiply them all together.)

This function has the property that $f_i(x_j)=0$ for $i\neq j$, but if $i=j$ then $$f_i(x) = A\cdot\prod_{j\neq i}(x_i-x_j).$$ Since we want that $f_i(x_i)=1$, let's just pick $A$ to make it hold: $$A = \prod_{j\neq i}\frac{1}{x_i-x_j} = \frac{1}{(x_i-x_0)(x_i-x_1)\dots(x_i-x_{i-1})(x_i-x_{i+1})\dots(x_i-x_n)}.$$ This is the part where we need to assume that the $x_j$'s are distinct; otherwise, we might be dividing by zero.

Putting everything together, we get that $f_i$ is $$f_i(x) = \prod_{j\neq i} \frac{x-x_j}{x_i-x_j}$$ and hence that $f$ is $$f(x) = \sum_{i=0}^n y_i\cdot\prod_{j\neq i} \frac{x-x_j}{x_i-x_j}.$$ This is a polynomial that interpolates between the given points, although as you noticed, its form is rather complicated.

• If I understand, I need to clarify my question; I was looking for some function that can be written as something like $f(x)=\ldots$, not as a piecewise/recursive function. (Is there a name for that type of function? An eqaution, perhaps?) – Conor O'Brien Jun 11 '15 at 21:09
• Oh, I see. In that case, you should probably look into Lagrange interpolation. Would you like me to say more about it, or is the Wikipedia page I linked to clear enough? – user134824 Jun 11 '15 at 21:10
• The wikipedia page seems to be a lot of murk. I'd love it if you could explain to me what it is to me, a (more or less) beginner. – Conor O'Brien Jun 11 '15 at 21:12
• Okay. Give me a few moments. – user134824 Jun 11 '15 at 21:12
• By the way, did you have any specific application or context for this question when you asked it? Interpolation is a very general problem, and there might be another interpolation method that is more useful to you. – user134824 Jun 11 '15 at 21:33